#1964

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find the Longest Valid Obstacle Course at Each Position

Compute the longest valid obstacle course at each position using binary search and careful array tracking techniques efficiently.

array binary search binary indexed tree

Problem Statement

You are given a 0-indexed integer array obstacles where obstacles[i] represents the height of the ith obstacle. For each position, you must determine the length of the longest non-decreasing sequence of obstacles ending at that position.

Return an array ans of the same length as obstacles, where ans[i] is the length of the longest valid obstacle course ending at index i. Each sequence must be non-decreasing and include obstacles[i] as its last element.

Examples

Example 1

Input: obstacles = [1,2,3,2]

Output: [1,2,3,3]

The longest valid obstacle course at each position is:

i = 0: [1], [1] has length 1.
i = 1: [1,2], [1,2] has length 2.
i = 2: [1,2,3], [1,2,3] has length 3.
i = 3: [1,2,3,2], [1,2,2] has length 3.

Example 2

Input: obstacles = [2,2,1]

Output: [1,2,1]

The longest valid obstacle course at each position is:

i = 0: [2], [2] has length 1.
i = 1: [2,2], [2,2] has length 2.
i = 2: [2,2,1], [1] has length 1.

Example 3

Input: obstacles = [3,1,5,6,4,2]

Output: [1,1,2,3,2,2]

The longest valid obstacle course at each position is:

i = 0: [3], [3] has length 1.
i = 1: [3,1], [1] has length 1.
i = 2: [3,1,5], [3,5] has length 2. [1,5] is also valid.
i = 3: [3,1,5,6], [3,5,6] has length 3. [1,5,6] is also valid.
i = 4: [3,1,5,6,4], [3,4] has length 2. [1,4] is also valid.
i = 5: [3,1,5,6,4,2], [1,2] has length 2.

Constraints

n == obstacles.length
1 <= n <= 105
1 <= obstacles[i] <= 107

Solution Approach

Binary Search over Course Lengths

Maintain an array where index j stores the minimum possible ending height for a course of length j+1. For each obstacle, perform binary search to find the longest course it can extend, then update the array. This ensures each update and query is efficient, leveraging the exact pattern of binary search over the valid answer space.

Dynamic Array Tracking

Track the minimum last height for each possible course length to handle non-decreasing sequences. Update the array carefully to ensure that later obstacles can extend existing sequences or start new longer courses, following the failure mode where neglecting update order could shorten sequences incorrectly.

Construct Answer Array

As you process each obstacle, record the course length found through binary search into ans[i]. This ensures the result directly reflects the longest valid obstacle course at each position and avoids miscounting sequences that cannot extend due to height constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) if using binary search for each obstacle to find its place in the tracking array. Space complexity is O(n) to store the tracking array and the result ans.

What Interviewers Usually Probe

Look for a binary search solution to handle large input sizes efficiently.
Consider how to maintain minimum heights per course length to extend sequences correctly.
Watch for edge cases where obstacles decrease or repeat, impacting sequence length.

Common Pitfalls or Variants

Common pitfalls

Failing to maintain the minimum height for each course length can produce shorter sequences than possible.
Using linear scan instead of binary search leads to TLE on large inputs.
Incorrectly updating the tracking array can overwrite valid sequences and reduce the final answer.

Follow-up variants

Find the longest strictly increasing obstacle course at each position.
Compute the total number of distinct valid obstacle courses ending at each index.
Determine the maximum obstacle course length if only adjacent elements can be used.

FAQ

What is the main pattern in Find the Longest Valid Obstacle Course at Each Position?

The main pattern is using binary search over the valid answer space to track the longest non-decreasing sequence ending at each index.

Can I solve this problem without binary search?

Yes, a naive O(n^2) approach using nested loops works but is inefficient for large n and exceeds time limits.

How do repeated obstacle heights affect the sequence?

Repeated heights can extend the non-decreasing sequence, so the tracking array must allow equal values in binary search.

What data structure helps optimize this problem?

An array storing the minimum ending height for each possible course length allows efficient binary search and updates.

Is this problem related to Longest Increasing Subsequence?

Yes, it generalizes LIS with non-decreasing sequences and requires tracking sequences ending at each position rather than overall maximum length.

terminal

Solution

Solution 1: Binary Indexed Tree (Fenwick Tree)

We can use a Binary Indexed Tree to maintain an array of the lengths of the longest increasing subsequences.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class BinaryIndexedTree:
    __slots__ = ["n", "c"]

    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, v: int):
        while x <= self.n:
            self.c[x] = max(self.c[x], v)
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x:
            s = max(s, self.c[x])
            x -= x & -x
        return s


class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        nums = sorted(set(obstacles))
        n = len(nums)
        tree = BinaryIndexedTree(n)
        ans = []
        for x in obstacles:
            i = bisect_left(nums, x) + 1
            ans.append(tree.query(i) + 1)
            tree.update(i, ans[-1])
        return ans

Continue Practicing

#2179 count good triplets in an array #2250 count number of rectangles containing each point #1649 create sorted array through instructions