LeetCode Problem 1964

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Binary Indexed Tree

Solution

LeetCode 1964, Find the Longest Valid Obstacle Course at Each Position

Problem Understanding

The problem gives an array obstacles, where each value represents the height of an obstacle. For every position i, we must determine the length of the longest valid obstacle course that ends exactly at index i.

A valid obstacle course must satisfy several conditions:

• We can only use obstacles from indices 0 through i
• The obstacle at index i must be included
• Obstacles must remain in their original order
• Heights must be non-decreasing, meaning every next obstacle is greater than or equal to the previous one

This is very similar to the classic Longest Increasing Subsequence problem, except there is one important difference:

• LIS requires strictly increasing values
• This problem allows equal values

That change affects the binary search condition and is the core detail that makes this problem tricky.

The output is an array ans where:

• ans[i] equals the length of the longest non-decreasing subsequence ending at i

The constraints are large:

• n can be up to 100000
• Heights can be up to 10^7

An O(n^2) dynamic programming solution will be far too slow. We need something around O(n log n).

Several edge cases are important:

• Arrays with all equal values
• Strictly decreasing arrays
• Strictly increasing arrays
• Repeated values mixed with increasing and decreasing segments
• Single-element arrays

The implementation must correctly handle duplicate heights because equality is allowed in the subsequence.

Approaches

Brute Force Dynamic Programming

A straightforward approach uses dynamic programming.

Define:

dp[i] = length of the longest valid obstacle course ending at i

For every index i, check all previous indices j < i.

If:

obstacles[j] <= obstacles[i]

then obstacle i can extend the sequence ending at j.

So:

dp[i] = max(dp[i], dp[j] + 1)

This works because we explicitly examine every valid previous obstacle.

However, the time complexity is O(n^2), which is too slow for n = 100000.

Optimal Binary Search Approach

The key insight comes from the Longest Increasing Subsequence optimization technique.

Instead of storing every subsequence, maintain an array called tails.

tails[length - 1] stores the minimum possible ending value of a non-decreasing subsequence of that length.

This structure allows binary search to efficiently determine where the current obstacle belongs.

The critical detail is that we need a non-decreasing subsequence, not a strictly increasing one.

Therefore:

• We search for the first value strictly greater than the current obstacle
• This is equivalent to upper_bound

Why?

Because equal values are allowed to extend the sequence.

For each obstacle:

• Find the insertion position using binary search
• That position plus one gives the answer for this index
• Update tails

This reduces the complexity to O(n log n).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Checks every previous obstacle for every position
Optimal	O(n log n)	O(n)	Uses LIS-style greedy strategy with binary search

Algorithm Walkthrough

Optimal Algorithm

1. Create an empty list called tails.

tails[k] will represent the minimum possible ending obstacle height for a valid non-decreasing subsequence of length k + 1. 2. Create the answer array ans. 3. Process each obstacle from left to right. 4. For the current obstacle height x, perform binary search on tails.

We search for the first position where:

tails[pos] > x

This is an upper bound search.

We do this because equal heights are allowed in the subsequence. 5. The insertion position determines the longest valid subsequence ending at this obstacle.

If the insertion position is pos, then:

ans[i] = pos + 1

6. Update tails.

• If pos equals the size of tails, append x
• Otherwise replace tails[pos] with x

Replacing keeps the subsequence ending values as small as possible, which maximizes future extension opportunities. 7. Continue until all obstacles are processed.

Why it works

The invariant is:

tails[k] = smallest possible ending value of a valid subsequence of length k + 1

Smaller ending values are always better because they allow more future obstacles to extend the subsequence.

Using upper bound ensures equal values can extend sequences, which matches the non-decreasing requirement.

Since each obstacle is placed at the longest valid position it can extend, the computed length is optimal for every index.

Python Solution

from bisect import bisect_right
from typing import List

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        tails = []
        answer = []

        for height in obstacles:
            position = bisect_right(tails, height)

            if position == len(tails):
                tails.append(height)
            else:
                tails[position] = height

            answer.append(position + 1)

        return answer

The implementation uses Python's built-in bisect_right, which performs the exact upper bound behavior we need.

tails maintains the smallest possible ending value for each subsequence length.

For every obstacle:

• bisect_right finds the first element greater than the current height
• The insertion index determines the subsequence length
• We either append or replace in tails

Replacing values does not lose valid solutions. It improves future possibilities by keeping ending values minimal.

The answer for each position is recorded immediately because the insertion position directly represents the longest valid subsequence ending there.

Go Solution

package main

import "sort"

func longestObstacleCourseAtEachPosition(obstacles []int) []int {
	tails := []int{}
	answer := make([]int, len(obstacles))

	for i, height := range obstacles {
		position := sort.Search(len(tails), func(j int) bool {
			return tails[j] > height
		})

		if position == len(tails) {
			tails = append(tails, height)
		} else {
			tails[position] = height
		}

		answer[i] = position + 1
	}

	return answer
}

The Go version uses sort.Search to implement upper bound behavior.

The condition:

tails[j] > height

finds the first value strictly greater than the current obstacle, exactly matching bisect_right in Python.

Slices in Go dynamically expand with append, making them suitable for maintaining tails.

Integer overflow is not a concern because sequence lengths are at most 100000.

Worked Examples

Example 1

obstacles = [1,2,3,2]

Step	Height	tails Before	Position	tails After	Answer
0	1	[]	0	[1]	1
1	2	[1]	1	[1,2]	2
2	3	[1,2]	2	[1,2,3]	3
3	2	[1,2,3]	2	[1,2,2]	3

Final result:

[1,2,3,3]

Example 2

obstacles = [2,2,1]

Step	Height	tails Before	Position	tails After	Answer
0	2	[]	0	[2]	1
1	2	[2]	1	[2,2]	2
2	1	[2,2]	0	[1,2]	1

Final result:

[1,2,1]

Example 3

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

Step	Height	tails Before	Position	tails After	Answer
0	3	[]	0	[3]	1
1	1	[3]	0	[1]	1
2	5	[1]	1	[1,5]	2
3	6	[1,5]	2	[1,5,6]	3
4	4	[1,5,6]	1	[1,4,6]	2
5	2	[1,4,6]	1	[1,2,6]	2

Final result:

[1,1,2,3,2,2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each obstacle performs one binary search
Space	O(n)	tails and answer array can grow to size n

The binary search on tails takes O(log n) time for each obstacle. Since there are n obstacles, the total complexity becomes O(n log n).

The tails array can grow to length n in the worst case of a fully increasing sequence, so the space complexity is O(n).

Test Cases

from typing import List
from bisect import bisect_right

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        tails = []
        answer = []

        for height in obstacles:
            position = bisect_right(tails, height)

            if position == len(tails):
                tails.append(height)
            else:
                tails[position] = height

            answer.append(position + 1)

        return answer

solution = Solution()

assert solution.longestObstacleCourseAtEachPosition([1,2,3,2]) == [1,2,3,3]  # provided example
assert solution.longestObstacleCourseAtEachPosition([2,2,1]) == [1,2,1]  # duplicate handling
assert solution.longestObstacleCourseAtEachPosition([3,1,5,6,4,2]) == [1,1,2,3,2,2]  # mixed ordering

assert solution.longestObstacleCourseAtEachPosition([1]) == [1]  # single element
assert solution.longestObstacleCourseAtEachPosition([1,2,3,4,5]) == [1,2,3,4,5]  # strictly increasing
assert solution.longestObstacleCourseAtEachPosition([5,4,3,2,1]) == [1,1,1,1,1]  # strictly decreasing

assert solution.longestObstacleCourseAtEachPosition([2,2,2,2]) == [1,2,3,4]  # all equal
assert solution.longestObstacleCourseAtEachPosition([1,3,2,2,4]) == [1,2,2,3,4]  # duplicates in middle

assert solution.longestObstacleCourseAtEachPosition([5,1,5,5,1,3,4,5,1,4]) == [1,1,2,3,2,3,4,5,3,5]  # stress mixed case

Test Summary

Test	Why
[1,2,3,2]	Validates basic example behavior
[2,2,1]	Confirms equal values extend sequences
[3,1,5,6,4,2]	Tests mixed increasing and decreasing values
[1]	Smallest valid input
[1,2,3,4,5]	Strictly increasing sequence
[5,4,3,2,1]	Strictly decreasing sequence
[2,2,2,2]	Ensures duplicates are handled correctly
[1,3,2,2,4]	Tests replacement logic in tails
Complex mixed test	Stresses correctness across many transitions

Edge Cases

All Elements Equal

Consider:

[2,2,2,2]

A common mistake is using lower bound instead of upper bound during binary search. Lower bound would prevent equal values from extending the sequence, producing incorrect results.

This implementation uses bisect_right or upper bound behavior, allowing each equal value to extend the subsequence correctly.

Strictly Decreasing Array

Consider:

[5,4,3,2,1]

Every obstacle can only form a subsequence of length 1.

The algorithm correctly replaces tails[0] repeatedly without increasing the size of tails.

This verifies that replacement logic is handled properly.

Strictly Increasing Array

Consider:

[1,2,3,4,5]

Every new obstacle extends the current longest subsequence.

The algorithm continuously appends to tails, producing answers:

[1,2,3,4,5]

This validates that the algorithm correctly grows the subsequence structure when extension is always possible.