Find the Longest Valid Obstacle Course at Each Position

Hard

Morgan Stanley

2 views

Topics:

ArraysBinary Search

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 i^th 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 i^th 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.length
1 <= n <= 10⁵
1 <= obstacles[i] <= 10⁷

Try coding it in LeetCode

Find the Longest Valid Obstacle Course at Each Position

Hard

Morgan Stanley

2 views

Topics:

ArraysBinary Search

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 i^th 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 i^th 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.length
1 <= n <= 10⁵
1 <= obstacles[i] <= 10⁷

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible height of an obstacle in the input array?
Can the input array be empty or contain null values? What should I return in those cases?
Are duplicate heights allowed in the obstacle course? If so, how should they be handled when determining the longest valid course?
Can you clarify the precise definition of a 'valid' obstacle course? Specifically, does each obstacle have to be strictly non-decreasing in height?
If there are multiple valid obstacle courses of the same maximum length ending at a certain position, should I return the length of any one of them, or is there a specific preference?

Brute Force Solution

Approach

The brute force approach to this obstacle course problem is like trying every single possible path for each obstacle. We'll consider all possible sub-courses that end at each position, and keep the best one seen so far.

Here's how the algorithm would work step-by-step:

For each obstacle, we consider all the obstacles that came before it, including itself.
For each of these 'sub-courses' ending at the current obstacle, we check if the obstacles are in increasing order of height (or the same height).
If the obstacles are in the correct order, we have a valid sub-course. We record the length of that sub-course.
If the obstacles are NOT in the correct order, we ignore this sub-course.
After checking all possible valid sub-courses ending at the current obstacle, we record the length of the longest one we found.
We repeat this process for every obstacle in the entire course.
Finally, we have the length of the longest valid obstacle course ending at each obstacle's position.

Code Implementation

def longest_obstacle_course_brute_force(obstacles):
    number_of_obstacles = len(obstacles)
    longest_courses = []

    for current_obstacle_index in range(number_of_obstacles):
        max_course_length = 0
        # Iterate through all sub-courses ending at the current obstacle
        for sub_course_end_index in range(current_obstacle_index + 1):
            
            sub_course = obstacles[:sub_course_end_index + 1]
            
            is_valid = True
            # Check if the current sub-course is monotonically increasing
            for i in range(len(sub_course) - 1):
                if sub_course[i] > sub_course[i + 1]:
                    is_valid = False
                    break

            if is_valid:
                # Record the length of the valid sub-course
                max_course_length = max(max_course_length, len(sub_course))
        
        longest_courses.append(max_course_length)

    return longest_courses

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through each of the n obstacles. For each obstacle, it considers all preceding obstacles, leading to a nested loop. Inside the inner loop, it checks if the 'sub-course' is valid, which requires iterating through the elements of that sub-course again to ensure they are in non-decreasing order. Thus, we have a nested loop structure with a third loop inside to perform the validation, leading to a time complexity of O(n³).

Space Complexity

O(1) – The provided plain English explanation outlines a brute force approach that considers sub-courses. However, the description doesn't explicitly state that it stores all sub-courses or their lengths. It only mentions recording the 'length of the longest one we found' for each position, which suggests only a single integer variable is used to keep track of the maximum length encountered so far for each obstacle, and possibly another to store the current obstacle's length. Since the algorithm only needs to store these length variables and doesn't create auxiliary data structures dependent on the input size N (number of obstacles), the space complexity remains constant. Therefore, the space complexity is O(1).

Optimal Solution

Approach

We want to find the length of the longest obstacle course ending at each obstacle. The key is to efficiently maintain a sorted list of the tallest obstacles we've seen so far and use that to determine the length of the valid course.

Here's how the algorithm would work step-by-step:

Imagine you're building a course one obstacle at a time.
Keep track of the possible endings of courses you've already seen. Think of this as a list of 'best' course endings, sorted by obstacle height.
For each new obstacle, see if it can extend the longest course seen so far. If it's taller than everything you've seen, then it makes the course one longer.
If the new obstacle is not the tallest, find the shortest existing 'best' course ending that is taller than or equal to the new obstacle. Replace that existing course ending with the new obstacle. This creates a shorter, valid course of same length.
The length of the longest obstacle course ending at the current obstacle is simply the size of our 'best' course ending list.

Code Implementation

def longest_obstacle_course_at_each_position(obstacles):
    longest_courses = []
    result = []

    for obstacle in obstacles:
        # Find the smallest obstacle in longest_courses >= current obstacle
        left, right = 0, len(longest_courses)
        while left < right:
            mid = (left + right) // 2
            if longest_courses[mid] <= obstacle:
                left = mid + 1
            else:
                right = mid

        # If obstacle extends the longest course, add it
        if left == len(longest_courses):
            longest_courses.append(obstacle)
        else:
            # Otherwise, replace a larger obstacle with the current one
            longest_courses[left] = obstacle

        # The length of the longest course ending at current obstacle is left + 1
        result.append(len(longest_courses))

    return result

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through each of the n obstacles in the input array once. Inside the loop, a binary search (or equivalent operation like upper_bound in C++ or bisect_right in Python) is performed on the 'best' course endings list to find the insertion point. Binary search has a time complexity of O(log k), where k is the current length of the 'best' course endings list. In the worst case, k can grow up to n. Therefore, the overall time complexity is O(n log n) because the O(log n) operation is performed for each of the n obstacles.

Space Complexity

O(N) – The algorithm maintains a list of 'best' course endings, sorted by obstacle height. In the worst-case scenario, where each obstacle is taller than the previous ones, this list will grow to store all N obstacles. Therefore, the auxiliary space required for this list is proportional to the input size N. This dominates any other constant space usage, so the overall space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return an empty array since there are no obstacles to form a course.
Array with a single obstacle	Return an array containing only '1' as the longest valid obstacle course is of length 1.
Array with obstacles of decreasing height	The longest valid course at each position will always be '1' since each obstacle breaks the increasing sequence.
Array with all obstacles of the same height	The longest valid course at each position will be the index + 1.
Large input array exceeding memory limits	The algorithm should be memory-efficient, ideally O(n) space, to handle reasonably large inputs without crashing.
Obstacle heights with extreme values (very large or very small)	Ensure the chosen data type (e.g., int) can accommodate the full range of obstacle heights to avoid overflow or underflow.
Array with duplicate obstacle heights interspersed throughout	The binary search and tail array update mechanism should handle duplicates correctly, extending the increasing subsequence as needed.
Obstacle heights are non-integer values (floating point)	If floats are permitted, ensure comparison logic accounts for potential floating-point precision errors.