What is the time complexity of LeetCode 1964. Find the Longest Valid Obstacle Course at Each Position?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 1964. Find the Longest Valid Obstacle Course at Each Position?

The Python solution on this page uses O(n) auxiliary space.

Find the Longest Valid Obstacle Course at Each Position — LeetCode 1964 Python Solution

HardBinary Indexed TreeArrayBinary Search

Problem: #1964
Pattern: Monotonic Stack
Reading time: 6 min
Source: leetcode.com

The problem

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.

Example

Input: obstacles = [1,2,3,2]
Output: [1,2,3,3]
Explanation: The longest valid obstacle course at each position is:

Python solution

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

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 1964. Find the Longest Valid Obstacle Course at Each Position is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1964. Find the Longest Valid Obstacle Course at Each Position?: LeetCode 1964. Find the Longest Valid Obstacle Course at Each Position is rated Hard on LeetCode.
What is the time complexity of LeetCode 1964. Find the Longest Valid Obstacle Course at Each Position?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 1964. Find the Longest Valid Obstacle Course at Each Position?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1964. Find the Longest Valid Obstacle Course at Each Position cover?: LeetCode 1964. Find the Longest Valid Obstacle Course at Each Position is tagged Binary Indexed Tree, Array and Binary Search on LeetCode.