Find the Longest Valid Obstacle Course at Each Position

Find the Longest Valid Obstacle Course at Each Position

What is this problem about?

The Find the Longest Valid Obstacle Course at Each Position interview question asks you to process an array of obstacle heights. For each position $i$, you need to find the length of the longest non-decreasing subsequence that ends at $i$ and includes the obstacle at $i$. This is essentially asking for the "Longest Increasing Subsequence" length for every prefix of the array.

Why is this asked in interviews?

Morgan Stanley and other financial firms use this problem to test your knowledge of efficient subsequence searching. The naive $O(N^2)$ LIS algorithm is too slow for large arrays. It evaluations your ability to implement the $O(N \log N)$ Binary Search interview pattern for LIS, which is a fundamental optimization in algorithmic competitive programming.

Algorithmic pattern used

This is a variation of the Longest Increasing Subsequence (LIS) problem solved using Patience Sorting or Binary Search.

1. Maintain a dynamic array tails where tails[i] is the smallest tail of all non-decreasing subsequences of length i+1.
2. For each height $H$ in the input:
   • Find the first element in tails that is strictly greater than $H$ using bisect_right or upper_bound.
   • If such an element exists, replace it with $H$.
   • If no such element exists, append $H$ to tails.
   • The length of the valid course ending at this position is the (index where $H$ was placed + 1).

Example explanation

Obstacles: [1, 2, 3, 2]

1. $H=1$: tails = [1]. Length = 1.
2. $H=2$: tails = [1, 2]. Length = 2.
3. $H=3$: tails = [1, 2, 3]. Length = 3.
4. $H=2$: Binary search for $> 2$ in [1, 2, 3] finds 3.
   • Replace 3: tails = [1, 2, 2].
   • $H$ was placed at index 2. Length = 3. Result: [1, 2, 3, 3].

Common mistakes candidates make

• Using standard DP: Implementing $O(N^2)$ LIS, which fails the time limit.
• Binary Search error: Using bisect_left (strictly increasing) instead of bisect_right (non-decreasing).
• Not returning all lengths: Only finding the global LIS instead of the LIS ending at each position.

Interview preparation tip

Understand the difference between "strictly increasing" and "non-decreasing" in LIS problems. It changes which binary search function you use (lower_bound vs upper_bound). This problem is a perfect exercise for the $O(N \log N)$ LIS algorithm.