1964. Find the Longest Valid Obstacle Course at Each Position

HardBinary Indexed TreeArrayBinary Search

Problem Description

The problem presents a scenario where we are given an array called obstacles, which represents the heights of obstacles in an obstacle course. The goal is to determine, for each position i in the array, the length of the longest sequence that can be formed including the ith obstacle and any number of preceding obstacles, with two conditions:

The sequence must include the ith obstacle.
Each obstacle in the sequence must be as tall or taller than the one before it. This means that the values in the chosen subsequence should be non-decreasing when read from left to right.

We need to perform this computation for every obstacle and return the lengths of these longest sequences in an array.

Intuition

The core challenge of this problem is efficiency. A naive approach examining all possible subsequences for each obstacle would be prohibitively slow because it would involve repeated work and have a high time complexity.

To efficiently solve the problem, we can use a Binary Indexed Tree (BIT), also known as a Fenwick Tree. This data structure is efficient for two types of operations that we need to perform:

Update operation: When we process an obstacle, we want to update the BIT so it reflects the maximum length of the obstacle course ending at this obstacle height.
Query operation: For a given obstacle, we want to know the maximum length of the obstacle course that can include this obstacle. In other words, we are interested in the "tallest" obstacle course that can be extended by the current obstacle without violating the non-decreasing height condition.

The intuition for this approach lies in transforming the original obstacle heights into a set of ranks such that we can use these ranks to update and query the BIT. For each obstacle, we query the BIT to find the length of the longest obstacle course that can be extended up to the current height, then we update the BIT at the rank position corresponding to the current obstacle's height, with the new maximum length considering the current obstacle.

Here's an overview of how the solution is designed:

Compression: Since obstacles may have any height, we first map each unique obstacle height to a unique rank in increasing order, which allows us to efficiently use the BIT.
BIT Initialisation: We initiate a BIT of length equal to the number of unique obstacle heights.
Traverse and Update: We then traverse the original obstacles array, for each element querying the BIT to find the length of the longest subsequence that it can extend, and then updating the BIT with this new length for future queries.
Result Construction: As we traverse the obstacles, we collect the lengths of the longest obstacle courses in an array that we will ultimately return as the result.

The result is an efficient algorithm that calculates the desired outcome for each obstacle in the array without redundant computations, thus significantly reducing time complexity compared to a brute-force approach.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The reference solution provided uses a Binary Indexed Tree (BIT) to keep track of the maximum obstacle course length for varying obstacle heights efficiently. The BIT is a data structure that provides methods to update an element as well as to calculate a prefix maximum in logarithmic time. Let's delve into how the solution employs BIT:

Rank Compression: Instead of dealing with potentially large obstacle height numbers, we compress the obstacle heights to a smaller range by assigning each unique height a unique rank. This mapping is achieved using a dictionary that pairs each height with its rank, which also helps us to access the ranks in constant time.
```
1s = sorted(set(obstacles))
2m = {v: i for i, v in enumerate(s, 1)}
```
BIT Creation: A BIT class is defined that can handle the update and query operations necessary for our solution. It uses one-based indexing as it makes the internal workings of the update and query operations easier to implement in BIT. There is an initialization method, a static lowbit function that calculates the least significant bit that is set, an update method to change the maximum course length for a given height (expressed as rank), and a query method to find the maximum course length up to a given height (rank inclusive).
```
1class BinaryIndexedTree:
2    ...
```
Updating and Querying the BIT: For each obstacle, we query the BIT to find the length of the longest subsequence that can include this obstacle based on its height, and then update the BIT with this new length.
```
1tree = BinaryIndexedTree(len(m))
2ans = []
3for v in obstacles:
4    x = m[v]
5    ans.append(1 + tree.query(x))
6    tree.update(x, ans[-1])
```
The tree.query(x) retrieves the length of the longest current obstacle course ending with a height that is equal to or less than that of the current obstacle. We add one to include the current obstacle itself. The tree.update(x, ans[-1]) changes the BIT so that it stores the length of the new longest sequence ending with the current obstacle's height.
Result Generation: As we iterate through the array, we construct the answer array ans by adding the length of the longest path at each step. This array ans is then returned as the solution.

By methodically updating the BIT as we process each obstacle and querying it for the information we need to calculate the course length at that step, we perform the necessary operations in a time-efficient manner. The BIT reduces the time complexity of updates and queries from linear to logarithmic, which is a significant improvement for large input arrays.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Heap sortMerge sortInsertion sortQuick sort

I don’t know

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the Binary Indexed Tree.

Suppose we have the following obstacles array:

1obstacles = [2, 1, 3, 2, 1, 5]

Step 1: Rank Compression

First, we need to compress the heights of the obstacles to a smaller range of ranks:

1s = sorted(set(obstacles))   # [1, 2, 3, 5]
2m = {v: i for i, v in enumerate(s, 1)}   # {1:1, 2:2, 3:3, 5:4}

Now each obstacle height has a corresponding rank:

Height 1 is mapped to rank 1.
Height 2 is mapped to rank 2.
Height 3 is mapped to rank 3.
Height 5 is mapped to rank 4.

Step 2: BIT Creation

We create a BIT to facilitate efficient update and query operations, with the initial state of:

1tree = BinaryIndexedTree(4)   # 4 is the number of unique heights.

Step 3: Updating and Querying the BIT

We traverse the obstacles array and for each obstacle:

Find the rank of the obstacle's height.
Query the BIT for the longest subsequence we can have with this obstacle's height or lower.
Update the BIT with the new longest sequence that includes this obstacle.

Traversing obstacles:

For obstacle with height 2:

Rank: 2
tree.query(2) returns 0, we add 1 to include this obstacle.
tree.update(2, 1) to reflect this obstacle as the end of a sequence of length 1.

For obstacle with height 1:

Rank: 1
tree.query(1) returns 0, we add 1 for this obstacle.
tree.update(1, 1) as the new longest subsequence length is 1.

For obstacle with height 3:

Rank: 3
tree.query(3) returns 1 since the longest sequence for ranks 1 or 2 is 1.
We add 1 (the height 3 obstacle itself) and get 2.
tree.update(3, 2) to update sequences ending with rank 3.

Continuing this process:

For 2 with rank 2:

tree.query(2) now returns 1 (from the first obstacle).
Adding this obstacle, ans.append(1 + 1) makes 2.
tree.update(2, 2) to update.

For 1 with rank 1:

tree.query(1) returns 1.
ans.append(1 + 0) makes 1 (the sequence doesn't extend).
No update needed as the current max ending at 1 is 1.

For 5 with rank 4:

tree.query(4) returns 2 (from either ranks 2 or 3).
ans.append(1 + 2) makes 3.
tree.update(4, 3) to update.

Step 4: Result Generation

The resultant ans through each step will be:

1ans = [1, 1, 2, 2, 1, 3]

This indicates the maximum length of non-decreasing sequence ending with each obstacle is 1, 1, 2, 2, 1, 3, respectively.

This example demonstrates how the solution efficiently calculates the length of the longest possible sequence for each position in obstacles using a BIT, with rank compression and optimized update and query operations.

Solution Implementation

1class BinaryIndexedTree:
2    def __init__(self, size):
3        # Initialize the size of Binary Indexed Tree and create a tree with 0 values.
4        self.size = size
5        self.tree = [0] * (size + 1)
6
7    @staticmethod
8    def lowbit(index):
9        # A method to obtain the lowest bit of an index.
10        return index & -index
11
12    def update(self, index, val):
13        # Update the tree with the value 'val' at the position 'index'.
14        while index <= self.size:
15            self.tree[index] = max(self.tree[index], val)
16            index += BinaryIndexedTree.lowbit(index)
17
18    def query(self, index):
19        # Query the current maximum value up to 'index'.
20        max_val = 0
21        while index > 0:
22            max_val = max(max_val, self.tree[index])
23            index -= BinaryIndexedTree.lowbit(index)
24        return max_val
25
26
27class Solution:
28    def longestObstacleCourseAtEachPosition(self, obstacles):
29        # Process each obstacle position to find the longest obstacle course at that position.
30        sorted_obstacles = sorted(set(obstacles))
31        # Create a mapping from obstacle height to tree index.
32        height_to_index = {height: idx for idx, height in enumerate(sorted_obstacles, start=1)}
33        tree = BinaryIndexedTree(len(height_to_index))
34        result = []
35
36        # For each obstacle 'obstacle_height' in the original list 'obstacles'.
37        for obstacle_height in obstacles:
38            # Get the index of the obstacle height in the tree.
39            tree_index = height_to_index[obstacle_height]
40            # Get the current maximum length at this index.
41            max_length = 1 + tree.query(tree_index)
42            # Append the maximum length to the result list.
43            result.append(max_length)
44            # Update the tree with the new max length for this index.
45            tree.update(tree_index, max_length)
46
47        return result
48
49# The 'List' type annotation is omitted as it should be imported with 
50# 'from typing import List' at the top of the file if type hinting is needed.
51

1class Solution {
2    public int lengthOfLIS(int[] nums) {
3        // A TreeSet to store the unique values in 'nums' in sorted order
4        TreeSet<Integer> sortedUniqueElements = new TreeSet<>();
5        for (int value : nums) {
6            sortedUniqueElements.add(value);
7        }
8        int index = 1;
9        // A mapping to store each value with its corresponding index
10        Map<Integer, Integer> valueToIndexMap = new HashMap<>();
11        for (int value : sortedUniqueElements) {
12            valueToIndexMap.put(value, index++);
13        }
14        // Initializing Binary Indexed Tree (Fenwick Tree) to help calculate LIS efficiently
15        BinaryIndexedTree tree = new BinaryIndexedTree(valueToIndexMap.size());
16        int maxLISLength = 1; // To keep track of the length of LIS
17        for (int value : nums) {
18            int mappedIndex = valueToIndexMap.get(value);
19            // Query the length of the longest increasing subsequence that ends with a number less than 'value'
20            int length = tree.query(mappedIndex - 1) + 1;
21            // Update the maximum length found so far
22            maxLISLength = Math.max(maxLISLength, length);
23            // Update the tree to reflect the new LIS length ending with 'value'
24            tree.update(mappedIndex, length);
25        }
26        // Return the length of the Longest Increasing Subsequence
27        return maxLISLength;
28    }
29}
30
31class BinaryIndexedTree {
32    private int size;
33    private int[] tree;
34
35    public BinaryIndexedTree(int size) {
36        this.size = size;
37        this.tree = new int[size + 1];
38    }
39
40    // Update the tree with the new value only if it is larger than the current value
41    public void update(int index, int value) {
42        while (index <= size) {
43            tree[index] = Math.max(tree[index], value);
44            index += lowBit(index);
45        }
46    }
47
48    // Query the maximum value in the tree up to the given index
49    public int query(int index) {
50        int maximum = 0;
51        while (index > 0) {
52            maximum = Math.max(maximum, tree[index]);
53            index -= lowBit(index);
54        }
55        return maximum;
56    }
57
58    // Method to compute the least significant bit (LSB) for a given index
59    public static int lowBit(int index) {
60        return index & -index;
61    }
62}
63

1#include <vector>
2#include <set>
3#include <unordered_map>
4#include <algorithm>
5
6using namespace std;
7
8// Definition for a Binary Indexed Tree (also known as a Fenwick Tree)
9class BinaryIndexedTree {
10public:
11    int size; // Size of the array representation
12    vector<int> tree; // The tree representation as a 1-indexed vector
13
14    // Constructor initializes the tree with a given size
15    BinaryIndexedTree(int n) : size(n), tree(n + 1, 0) {}
16
17    // Updates the value at position 'x' with the value 'val' along the tree
18    void update(int x, int val) {
19        while (x <= size) {
20            tree[x] = max(tree[x], val); // Take the maximum value at each node
21            x += lowbit(x); // Move to the next index to update
22        }
23    }
24
25    // Queries the maximum value from the start up to position 'x'
26    int query(int x) {
27        int result = 0;
28        while (x > 0) {
29            result = max(result, tree[x]); // Take the maximum value along the path
30            x -= lowbit(x); // Move to the parent node
31        }
32        return result;
33    }
34
35    // Computes the lowest significant bit of 'x'
36    int lowbit(int x) {
37        return x & -x;
38    }
39};
40
41class Solution {
42public:
43    // For each position, calculate the longest obstacle course length upto that position
44    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
45        set<int> sortedObstacles(obstacles.begin(), obstacles.end());
46        int index = 1;
47        unordered_map<int, int> obstacleToIndex;
48        // Map each obstacle value to a unique index
49        for (int obstacle : sortedObstacles) obstacleToIndex[obstacle] = index++;
50
51        // Create a BinaryIndexedTree with size equal to number of unique obstacles
52        BinaryIndexedTree tree(obstacleToIndex.size());
53        int totalObstacles = obstacles.size();
54        vector<int> answer(totalObstacles);
55
56        // Iterate over the obstacle positions
57        for (int i = 0; i < totalObstacles; ++i) {
58            int currentValue = obstacles[i];
59            int mappedIndex = obstacleToIndex[currentValue];
60            // The longest obstacle length at position 'i' is 1 more than the maximum
61            // length found in the tree for any obstacle value less than or equal to 'currentValue'
62            answer[i] = 1 + tree.query(mappedIndex);
63            // Update the tree with the new longest length found for 'currentValue'
64            tree.update(mappedIndex, answer[i]);
65        }
66
67        return answer;
68    }
69};
70

1// A global declaration for size and the binary indexed tree (Fenwick Tree)
2let size: number;
3let tree: number[];
4
5// Initializes the tree with a given size
6function init(n: number): void {
7    size = n;
8    tree = Array(n + 1).fill(0);
9}
10
11// Updates the value at position `x` with the value `val` along the tree
12function update(x: number, val: number): void {
13    while (x <= size) {
14        tree[x] = Math.max(tree[x], val); // Take the maximum value at each node
15        x += lowbit(x); // Move to the next index to update
16    }
17}
18
19// Queries the maximum value from the start up to position `x`
20function query(x: number): number {
21    let result = 0;
22    while (x > 0) {
23        result = Math.max(result, tree[x]); // Take the maximum value along the path
24        x -= lowbit(x); // Move to the parent node
25    }
26    return result;
27}
28
29// Computes the lowest significant bit of `x`
30function lowbit(x: number): number {
31    return x & -x;
32}
33
34// For each position, calculate the longest obstacle course length up to that position
35function longestObstacleCourseAtEachPosition(obstacles: number[]): number[] {
36    const sortedObstacles: Set<number> = new Set(obstacles);
37    let index: number = 1;
38    const obstacleToIndex: Map<number, number> = new Map();
39    // Map each obstacle value to a unique index
40    sortedObstacles.forEach(obstacle => {
41        obstacleToIndex.set(obstacle, index++);
42    });
43
44    // Initialize a BinaryIndexedTree with size equal to number of unique obstacles
45    init(obstacleToIndex.size);
46    const totalObstacles: number = obstacles.length;
47    const answer: number[] = [];
48
49    // Iterate over the obstacle positions
50    for (let i = 0; i < totalObstacles; ++i) {
51        const currentValue: number = obstacles[i];
52        const mappedIndex: number = obstacleToIndex.get(currentValue) || 0;
53        // The longest obstacle length at position `i` is 1 more than the maximum
54        // length found in the tree for any obstacle value less than or equal to `currentValue`
55        answer[i] = 1 + query(mappedIndex);
56        // Update the tree with the new longest length found for `currentValue`
57        update(mappedIndex, answer[i]);
58    }
59
60    return answer;
61}
62

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The time complexity of the longestObstacleCourseAtEachPosition method is determined by several factors:

Sorting the unique values of obstacles: This has a complexity of O(U log U) where U is the number of unique values in the obstacles list. Sorting is done using sorted() which typically employs Timsort.
Building the mapping, m: This involves iterating over the sorted unique values once, which gives us O(U).
Binary Indexed Tree (BIT) operations:
- Update: For each obstacle, we call update, which results in O(log N) operations for each update where N is the length of the BIT array.
- Query: Similarly, each query is an O(log N) operation.

If there are O obstacles in the input list and assuming that N ≈ U (since the BIT array length is based on the number of unique values), the combined complexity for the BIT operations for all obstacles is O(O log U).

Combining everything, the total time complexity is O(U log U) + O(U) + O(O log U). Considering that U can be at most O, and O is usually larger than U, this simplifies to O(O log O).

Space Complexity

The space complexity of the longestObstacleCourseAtEachPosition method is influenced by several data structures:

Sorted list of unique values: Requires O(U) space.
Mapping m: Also requires O(U) space to maintain the mapping from value to index.
Binary Indexed Tree (BIT): Requires O(N) space, where N is the length of the BIT array which is roughly equivalent to the number of unique obstacles, O(U).

The space taken by the output list ans is O(O) where O is the number of obstacles.

So the overall space complexity is O(U) + O(U) + O(O), which simplifies to O(O) since again, O is usually larger than U.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1964. Find the Longest Valid Obstacle Course at Each Position

Problem Description

Intuition

Solution Approach

Example Walkthrough

Step 1: Rank Compression

Step 2: BIT Creation

Step 3: Updating and Querying the BIT

Step 4: Result Generation

Solution Implementation

Time and Space Complexity