{x}
blog image

Find the Longest Valid Obstacle Course at Each Position

You want to build some obstacle courses. You are given a 0-indexed integer array obstacles of length n, where obstacles[i] describes the height of the ith obstacle.

For every index i between 0 and n - 1 (inclusive), find the length of the longest obstacle course in obstacles such that:

  • You choose any number of obstacles between 0 and i inclusive.
  • You must include the ith obstacle in the course.
  • You must put the chosen obstacles in the same order as they appear in obstacles.
  • Every obstacle (except the first) is taller than or the same height as the obstacle immediately before it.

Return an array ans of length n, where ans[i] is the length of the longest obstacle course for index i as described above.

 

Example 1:

Input: obstacles = [1,2,3,2]
Output: [1,2,3,3]
Explanation: 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]
Explanation: 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]
Explanation: 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 Explanation: Find the Longest Valid Obstacle Course at Each Position

This problem asks to find the length of the longest valid obstacle course ending at each position in the input array obstacles. A valid obstacle course is a non-decreasing subsequence of obstacles.

The most efficient solution uses a Binary Indexed Tree (BIT), also known as a Fenwick Tree. Here's a breakdown:

1. Understanding the BIT:

A BIT is a data structure that efficiently handles range sum queries and updates. In this context, we'll use it to store and query the lengths of the longest non-decreasing subsequences ending at various heights. The index in the BIT represents the height of an obstacle (after sorting unique heights), and the value at that index represents the length of the longest non-decreasing subsequence ending at that height or less.

2. Algorithm:

  1. Sort Unique Heights: First, create a sorted list of unique obstacle heights. This allows us to use the heights as indices in the BIT.

  2. Iterate Through Obstacles: The algorithm iterates through the original obstacles array. For each obstacle:

    • Binary Search (or equivalent): Find the index i in the sorted unique heights list where the current obstacle's height would be inserted to maintain sorted order. This essentially tells us what the height of the previous obstacle must be at maximum.

    • BIT Query: Use the BIT's query(i) function to find the maximum length of a non-decreasing subsequence ending at a height less than or equal to the current obstacle's height. This represents the length of the longest valid course before adding the current obstacle.

    • Update BIT: Add 1 to the result of the query (to include the current obstacle) and update the BIT with this new length at index i. This updates the maximum length of the sequence achievable ending with that height or lower.

    • Store Result: Store the updated length in the ans array at the corresponding index.

3. Time and Space Complexity:

  • Time Complexity: O(n log n). The sorting takes O(n log n) time. Each obstacle requires a binary search (O(log n)) and a BIT update (O(log n)), resulting in an overall O(n log n) time complexity.

  • Space Complexity: O(n). The BIT requires space proportional to the number of unique obstacle heights, which is at most n. The ans array also uses O(n) space.

4. Code Examples (Python, Java, C++, Go, TypeScript):

The code examples in the provided response demonstrate the solution using different programming languages. They all follow the algorithm described above, using a custom BinaryIndexedTree class and leveraging efficient searching mechanisms (binary search or its equivalents in each language). Note that the Python solution uses the bisect module's bisect_left for efficient insertion point finding.

5. Example Walkthrough (Example 1): obstacles = [1, 2, 3, 2]

  1. Unique sorted heights: [1, 2, 3]
  2. Iteration 1 (obstacle 1):
    • i (index of 1) = 1. query(1) = 0. ans[0] = 0 + 1 = 1. Update BIT at index 1 with value 1.
  3. Iteration 2 (obstacle 2):
    • i (index of 2) = 2. query(2) = 1. ans[1] = 1 + 1 = 2. Update BIT at index 2 with value 2.
  4. Iteration 3 (obstacle 3):
    • i (index of 3) = 3. query(3) = 2. ans[2] = 2 + 1 = 3. Update BIT at index 3 with value 3.
  5. Iteration 4 (obstacle 2):
    • i (index of 2) = 2. query(2) = 2. ans[3] = 2 + 1 = 3. Update BIT at index 2 with value 2 (no change, as 2 is already there).

The final ans array is [1, 2, 3, 3].

The provided code examples efficiently implement this algorithm, achieving optimal time complexity for solving this problem. Remember that the BIT is crucial for efficient querying and updating of the maximum lengths of subsequences.