We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Longest Valid Obstacle Course at Each Position

Number: 2096

Difficulty: Hard

Paid? No

Companies: Morgan Stanley

Problem Description

Given an array of integers obstacles, for every index i (from 0 to n-1) determine the length of the longest non-decreasing subsequence (while preserving the order of appearance) ending at i. The subsequence must include obstacles[i] and may include any of the previous obstacles as long as each element is not less than the previous one.

Key Insights

  • The problem can be viewed as computing a longest non-decreasing subsequence (LNDS) for each index.
  • Instead of computing a classic LNDS for the whole array, we compute it incrementally for each position.
  • A variation of the patience sorting algorithm is used with binary search.
  • Maintain a dynamic array (dp) where dp[i] stores the minimal possible ending value for a non-decreasing subsequence of length i+1.
  • Use binary search with a modification (finding the rightmost position where obstacles[i] can be placed) since equal values are allowed.
  • The result for each index i is the insertion position (1-indexed) in this dp array.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of obstacles since each index uses a binary search. Space Complexity: O(n), for storing the dp array and the answer array.

Solution

We traverse the obstacles array sequentially. At each index, we perform a binary search on a maintained dp array to determine the correct position to insert or replace an element, ensuring that dp remains sorted non-decreasingly. Since obstacles must be non-decreasing (equal values allowed), we use a binary search that finds the first element greater than obstacles[i] (upper bound), rather than strictly greater than or equal. This gives the length of the longest valid subsequence ending at that position, which we record. Updating dp accordingly ensures that subsequent binary searches consider the smallest ending values possible for subsequences of various lengths.

Code Solutions

# Python solution using binary search (bisect)
import bisect

def longestObstacleCourseAtEachPosition(obstacles):
    # dp stores the smallest ending obstacle for a course of length i+1 at dp[i]
    dp = []
    result = []
    
    for height in obstacles:
        # Perform binary search to find the rightmost index where height can be placed
        # Since we allow equal values, we search for the first element that is greater than height.
        pos = bisect.bisect_right(dp, height)
        # If pos is at the end, append the height; otherwise update dp[pos]
        if pos == len(dp):
            dp.append(height)
        else:
            dp[pos] = height
        # The length of the longest valid course ending at current index is pos + 1
        result.append(pos + 1)
    
    return result

# Example usage:
# print(longestObstacleCourseAtEachPosition([1,2,3,2]))  # Expected output: [1,2,3,3]
← Back to All Questions