---
comments: true
difficulty: Hard
edit_url: https://github.com/doocs/leetcode/edit/main/solution/1900-1999/1964.Find%20the%20Longest%20Valid%20Obstacle%20Course%20at%20Each%20Position/README_EN.md
rating: 1933
source: Weekly Contest 253 Q4
tags:
- Binary Indexed Tree
- Array
- Binary Search
---
# [1964. Find the Longest Valid Obstacle Course at Each Position](https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position)
[中文文档](/solution/1900-1999/1964.Find%20the%20Longest%20Valid%20Obstacle%20Course%20at%20Each%20Position/README.md)
## Description
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.length1 <= n <= 1051 <= obstacles[i] <= 107
## Solutions
### Solution 1: Binary Indexed Tree (Fenwick Tree)
We can use a Binary Indexed Tree to maintain an array of the lengths of the longest increasing subsequences.
Then for each obstacle, we query in the Binary Indexed Tree for the length of the longest increasing subsequence that is less than or equal to the current obstacle, suppose it is $l$. Then the length of the longest increasing subsequence of the current obstacle is $l+1$. We add $l+1$ to the answer array, and update $l+1$ in the Binary Indexed Tree.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the number of obstacles.
#### Python3
```python
class BinaryIndexedTree:
__slots__ = ["n", "c"]
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, v: int):
while x <= self.n:
self.c[x] = max(self.c[x], v)
x += x & -x
def query(self, x: int) -> int:
s = 0
while x:
s = max(s, self.c[x])
x -= x & -x
return s
class Solution:
def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
nums = sorted(set(obstacles))
n = len(nums)
tree = BinaryIndexedTree(n)
ans = []
for x in obstacles:
i = bisect_left(nums, x) + 1
ans.append(tree.query(i) + 1)
tree.update(i, ans[-1])
return ans
```
#### Java
```java
class BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
c = new int[n + 1];
}
public void update(int x, int v) {
while (x <= n) {
c[x] = Math.max(c[x], v);
x += x & -x;
}
}
public int query(int x) {
int s = 0;
while (x > 0) {
s = Math.max(s, c[x]);
x -= x & -x;
}
return s;
}
}
class Solution {
public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
int[] nums = obstacles.clone();
Arrays.sort(nums);
int n = nums.length;
int[] ans = new int[n];
BinaryIndexedTree tree = new BinaryIndexedTree(n);
for (int k = 0; k < n; ++k) {
int x = obstacles[k];
int i = Arrays.binarySearch(nums, x) + 1;
ans[k] = tree.query(i) + 1;
tree.update(i, ans[k]);
}
return ans;
}
}
```
#### C++
```cpp
class BinaryIndexedTree {
private:
int n;
vector c;
public:
BinaryIndexedTree(int n) {
this->n = n;
c = vector(n + 1);
}
void update(int x, int v) {
while (x <= n) {
c[x] = max(c[x], v);
x += x & -x;
}
}
int query(int x) {
int s = 0;
while (x > 0) {
s = max(s, c[x]);
x -= x & -x;
}
return s;
}
};
class Solution {
public:
vector longestObstacleCourseAtEachPosition(vector& obstacles) {
vector nums = obstacles;
sort(nums.begin(), nums.end());
int n = nums.size();
vector ans(n);
BinaryIndexedTree tree(n);
for (int k = 0; k < n; ++k) {
int x = obstacles[k];
auto it = lower_bound(nums.begin(), nums.end(), x);
int i = distance(nums.begin(), it) + 1;
ans[k] = tree.query(i) + 1;
tree.update(i, ans[k]);
}
return ans;
}
};
```
#### Go
```go
type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
return &BinaryIndexedTree{n, make([]int, n+1)}
}
func (bit *BinaryIndexedTree) update(x, v int) {
for x <= bit.n {
bit.c[x] = max(bit.c[x], v)
x += x & -x
}
}
func (bit *BinaryIndexedTree) query(x int) (s int) {
for x > 0 {
s = max(s, bit.c[x])
x -= x & -x
}
return
}
func longestObstacleCourseAtEachPosition(obstacles []int) (ans []int) {
nums := slices.Clone(obstacles)
sort.Ints(nums)
n := len(nums)
tree := NewBinaryIndexedTree(n)
for k, x := range obstacles {
i := sort.SearchInts(nums, x) + 1
ans = append(ans, tree.query(i)+1)
tree.update(i, ans[k])
}
return
}
```
#### TypeScript
```ts
class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
update(x: number, v: number): void {
while (x <= this.n) {
this.c[x] = Math.max(this.c[x], v);
x += x & -x;
}
}
query(x: number): number {
let s = 0;
while (x > 0) {
s = Math.max(s, this.c[x]);
x -= x & -x;
}
return s;
}
}
function longestObstacleCourseAtEachPosition(obstacles: number[]): number[] {
const nums: number[] = [...obstacles];
nums.sort((a, b) => a - b);
const n: number = nums.length;
const ans: number[] = [];
const tree: BinaryIndexedTree = new BinaryIndexedTree(n);
const search = (x: number): number => {
let [l, r] = [0, n];
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (let k = 0; k < n; ++k) {
const i: number = search(obstacles[k]) + 1;
ans[k] = tree.query(i) + 1;
tree.update(i, ans[k]);
}
return ans;
}
```