Find the Longest Valid Obstacle Course at Each Position

hard array binary search dp

Problem

You are given an array obstacles of heights. You walk left to right and, at every position i, you want to build the longest possible obstacle course that ends at position i. A valid course picks obstacles in increasing index order whose heights are non-decreasing (each chosen obstacle is at least as tall as the previous one), and the last chosen obstacle must be the one at i. For every position, return the length of that longest valid course.

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

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

At index 3 (height 6) the longest course is [3, 5, 6] (or [1, 5, 6]), length 3. At index 4 (height 4) the best is [3, 4] or [1, 4], length 2.

obstacles (comma-separated)

def longest_obstacle_course(obstacles):
    tails = []
    ans = []
    for h in obstacles:
        lo, hi = 0, len(tails)
        while lo < hi:
            mid = (lo + hi) // 2
            if tails[mid] <= h: lo = mid + 1
            else: hi = mid
        if lo == len(tails): tails.append(h)
        else: tails[lo] = h
        ans.append(lo + 1)
    return ans

function longestObstacleCourse(obstacles) {
  const tails = [], ans = [];
  for (const h of obstacles) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] <= h) lo = mid + 1;
      else hi = mid;
    }
    if (lo === tails.length) tails.push(h);
    else tails[lo] = h;
    ans.push(lo + 1);
  }
  return ans;
}

class Solution {
    public int[] longestObstacleCourse(int[] obstacles) {
        int n = obstacles.length, len = 0;
        int[] tails = new int[n], ans = new int[n];
        for (int i = 0; i < n; i++) {
            int h = obstacles[i], lo = 0, hi = len;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] <= h) lo = mid + 1;
                else hi = mid;
            }
            if (lo == len) tails[len++] = h;
            else tails[lo] = h;
            ans[i] = lo + 1;
        }
        return ans;
    }
}

vector<int> longestObstacleCourse(vector<int>& obstacles) {
    vector<int> tails, ans;
    for (int h : obstacles) {
        int lo = 0, hi = (int)tails.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (tails[mid] <= h) lo = mid + 1;
            else hi = mid;
        }
        if (lo == (int)tails.size()) tails.push_back(h);
        else tails[lo] = h;
        ans.push_back(lo + 1);
    }
    return ans;
}

Explanation

For each index we need the length of the longest non-decreasing run that ends exactly there. That is the classic "longest non-decreasing subsequence" problem, but answered for every prefix as we go. The fast way uses a tails array, the same trick that powers patience sorting.

tails[k] holds the smallest possible ending height of any valid course of length k + 1 seen so far. This array is always sorted in non-decreasing order. When a new height h arrives, we binary-search for the first slot whose stored value is strictly greater than h (a bisect_right / upper-bound search, because using <= lets equal heights extend a course).

If that position is past the end of tails, then h extends the longest course so far, so we append it. Otherwise we overwrite tails[pos] with h — we have found a course of that same length that ends on a smaller (or equal) height, which is never worse for the future. Either way the index pos tells us how many obstacles sit at or below h in the increasing structure, so the answer for this position is pos + 1.

Trace [3, 1, 5, 6, 4, 2]: 3 → tails [3], ans 1. 1 overwrites slot 0 → [1], ans 1. 5 appends → [1, 5], ans 2. 6 appends → [1, 5, 6], ans 3. 4 lands at slot 1 → [1, 4, 6], ans 2. 2 lands at slot 1 → [1, 2, 6], ans 2. Output [1, 1, 2, 3, 2, 2].

The crucial detail is the upper-bound (<=) comparison: a lower-bound search would reject equal heights and instead solve the strictly-increasing version. Because heights are allowed to repeat in a valid course, we must keep equal values, so bisect_right is the right tool.

Time: O(n log n) Space: O(n)