1964

1964. Find the Longest Valid Obstacle Course at Each Position (Hard)

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

Similar Questions:

• Longest Increasing Subsequence (Medium)

Solution 1. Binary Search (Regret Greedy)

Intuition: A classic extension of 300. Longest Increasing Subsequence (Medium) whose optimal solution is regret greedy + binary search. You can find the explanation in my note

Algorithm:

Assume we have a vector<int> lis which stands for the longest increasing subsequence. lis is initially empty and is always sorting in ascending order.

For each A[i], we find the first lis[j] > A[i] by binary searching in the entire lis, and set lis[j] = A[i]. The length of the LIS ending with A[i] is j + 1, i.e. ans[i] = j + 1.

// OJ: https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& A) {
        vector<int> ans, lis;
        for (int n : A) {
            int i = upper_bound(begin(lis), end(lis), n) - begin(lis);
            if (i == lis.size()) lis.push_back(n);
            else lis[i] = n;
            ans.push_back(i + 1);
        }
        return ans;
    }
};

We can use len to keep track of the length of lis, and reuse A to store the lis values.

// OJ: https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& A) {
        vector<int> ans;
        int len = 0;
        for (int n : A) {
            int i = upper_bound(begin(A), begin(A) + len, n) - begin(A); // this number `n` should be put at `lis[i]`
            A[i] = n;
            len = max(i + 1, len); // updating the length of LIS
            ans.push_back(i + 1);
        }
        return ans;
    }
};

Follow-up: 1671. Minimum Number of Removals to Make Mountain Array (Hard) is a great bidirectional extension of this problem.