1964. Find the Longest Valid Obstacle Course at Each Position LeetCode Solution
In this guide, you will get 1964. Find the Longest Valid Obstacle Course at Each Position LeetCode Solution with the best time and space complexity. The solution to Find the Longest Valid Obstacle Course at Each Position problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(n)
1964. Find the Longest Valid Obstacle Course at Each Position LeetCode Solution in C++
class Solution {
public:
// Similar to 300. Longest Increasing Subsequence
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
vector<int> ans;
// tails[i] := the minimum tail of all the increasing subsequences having
// length i + 1
vector<int> tails;
for (const int obstacle : obstacles)
if (tails.empty() || obstacle >= tails.back()) {
tails.push_back(obstacle);
ans.push_back(tails.size());
} else {
const int index = firstGreater(tails, obstacle);
tails[index] = obstacle;
ans.push_back(index + 1);
}
return ans;
}
private:
int firstGreater(const vector<int>& arr, int target) {
return ranges::upper_bound(arr, target) - arr.begin();
}
}; /* code provided by PROGIEZ */
1964. Find the Longest Valid Obstacle Course at Each Position LeetCode Solution in Java
class Solution {
// Similar to 300. Longest Increasing Subsequence
public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
List<Integer> ans = new ArrayList<>();
// tails[i] := the minimum tail of all the increasing subsequences with
// length i + 1
List<Integer> tails = new ArrayList<>();
for (final int obstacle : obstacles)
if (tails.isEmpty() || obstacle >= tails.get(tails.size() - 1)) {
tails.add(obstacle);
ans.add(tails.size());
} else {
final int index = firstGreater(tails, obstacle);
tails.set(index, obstacle);
ans.add(index + 1);
}
return ans.stream().mapToInt(Integer::intValue).toArray();
}
private int firstGreater(List<Integer> arr, int target) {
int l = 0;
int r = arr.size();
while (l < r) {
final int m = (l + r) / 2;
if (arr.get(m) > target)
r = m;
else
l = m + 1;
}
return l;
}
} // code provided by PROGIEZ
1964. Find the Longest Valid Obstacle Course at Each Position LeetCode Solution in Python
class Solution:
# Similar to 300. Longest Increasing Subsequence
def longestObstacleCourseAtEachPosition(
self, obstacles: list[int],
) -> list[int]:
ans = []
# tails[i] := the minimum tail of all the increasing subsequences having
# length i + 1
tails = []
for obstacle in obstacles:
if not tails or obstacle >= tails[-1]:
tails.append(obstacle)
ans.append(len(tails))
else:
index = bisect.bisect_right(tails, obstacle)
tails[index] = obstacle
ans.append(index + 1)
return ans # code by PROGIEZ
