Sponsored
Sponsored
In this approach, we use a combination of dynamic programming and binary search to find the longest obstacle course at each position. We maintain a list which helps to track the longest increasing subsequence (LIS) up to the current index. For each obstacle, we find its position in the LIS using binary search (which keeps it sorted), updating the LIS while also determining the length of the LIS at each step.
Time Complexity: O(n log n), as each binary search operation runs in O(log n) and is performed n times. Space Complexity: O(n), storing the longest sequence lengths.
1#include <vector>
2#include <algorithm>
3
4std::vector<int> longestObstacleCourseAtEachPosition(std::vector<int>& obstacles) {
5 std::vector<int> lis, ans(obstacles.size());
6 for (int i = 0; i < obstacles.size(); ++i) {
7 int pos = std::upper_bound(lis.begin(), lis.end(), obstacles[i]) - lis.begin();
8 ans[i] = pos + 1;
9 if (pos == lis.size()) lis.push_back(obstacles[i]);
10 else lis[pos] = obstacles[i];
11 }
12 return ans;
13}This C++ solution utilizes std::upper_bound to perform its binary search-like capability, updating the lis vector accordingly.
This approach uses a Fenwick Tree (or BIT) to keep track of the lengths of obstacle courses efficiently. As we iterate through the obstacles array, we update our Fenwick Tree with the longest course length ending at each obstacle using range queries.
Time Complexity: O(n log m), where m is the maximum obstacle height. Space Complexity: O(m).
1class FenwickTree:
2 def __init__(self,
This Python code defines a Fenwick Tree class to support efficient updates and queries. The main function iterates over the obstacles, with each step updating and querying the Fenwick Tree for the current obstacle height, ensuring optimal performance.