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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Longest Valid Obstacle Course at Each Position

Difficulty: Hard

Problem 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 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.

Key Insights

  • The problem can be approached as a variation of the Longest Increasing Subsequence (LIS) problem, where we allow equal heights.
  • We maintain a dynamic programming array (or a list) that helps track the longest valid obstacle course ending at each position.
  • Binary Search can be used to efficiently find the position to update in our dynamic list, allowing us to maintain the properties of the longest valid subsequence.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

To solve this problem, we utilize a dynamic programming approach combined with binary search. We maintain a list that represents the current state of the longest obstacle course that can be formed up to the current index. For each obstacle, we determine its position in this list using binary search, and we either extend the list or update an existing position. This ensures that we can efficiently calculate the length of the longest valid obstacle course at each position in the input array.

Code Solutions

from bisect import bisect_right

def longestObstacleCourseAtEachPosition(obstacles):
    n = len(obstacles)
    dp = []  # This will store the current valid increasing sequence
    ans = [0] * n  # Result array

    for i in range(n):
        pos = bisect_right(dp, obstacles[i])  # Find the position to replace or extend
        if pos < len(dp):
            dp[pos] = obstacles[i]  # Replace the element
        else:
            dp.append(obstacles[i])  # Extend the list
        ans[i] = pos + 1  # Length of the valid course ending at index i
    
    return ans
← Back to All Questions