Find the Longest Valid Obstacle Course at Each Position

Find the Longest Valid Obstacle Course at Each Position - 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 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.

Input & Output

Example 1 — Basic Sequence

$ Input: obstacles = [1,2,3,2]

› Output: [1,2,3,2]

💡 Note: At index 0: longest course is [1] with length 1. At index 1: longest course is [1,2] with length 2. At index 2: longest course is [1,2,3] with length 3. At index 3: longest course is [1,2] with length 2 (can't include 3 since 3 > 2).

Example 2 — Decreasing Sequence

$ Input: obstacles = [2,2,1]

› Output: [1,2,1]

💡 Note: At index 0: longest course is [2] with length 1. At index 1: longest course is [2,2] with length 2. At index 2: longest course is [1] with length 1 (can't use previous obstacles since they're taller).

Example 3 — All Same Heights

$ Input: obstacles = [3,1,5,6,4,2]

› Output: [1,1,2,3,2,2]

💡 Note: At each position, we find the longest non-decreasing subsequence ending at that position. For example, at index 3 (value 6), the longest course is [1,5,6] with length 3.

Constraints

1 ≤ obstacles.length ≤ 10⁵
1 ≤ obstacles[i] ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

Array of obstacle heights: [1,2,3,2]

Process

For each position, find longest valid course ending there

Output

Array of lengths: [1,2,3,2]

Key Takeaway

🎯 Key Insight: This is a variation of Longest Increasing Subsequence where we find the longest non-decreasing sequence ending at each position

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

This problem is a variant of the Longest Increasing Subsequence (LIS) where we need to find the longest non-decreasing subsequence ending at each position. The key insight is to use binary search with patience sorting to efficiently maintain the smallest tail element for each possible length. Best approach is Binary Search with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Dynamic Programming	O(n²)	O(n)	For each position, check all previous positions to find longest valid sequence
Binary Search with Patience Sorting	O(n log n)	O(n)	Use binary search to efficiently find insertion point in longest increasing subsequence

Brute Force Dynamic Programming — Algorithm Steps

Initialize DP array with all 1s
For each position i, check all previous positions j
If obstacles[j] <= obstacles[i], update dp[i] = max(dp[i], dp[j] + 1)

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[i] = 1 for all positions

Compare

For each position, check all previous positions

Update

If valid, update dp[i] = max(dp[i], dp[j] + 1)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* obstacles, int n, int* returnSize) {
    *returnSize = n;
    int* dp = (int*)malloc(n * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (obstacles[j] <= obstacles[i]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }
    
    return dp;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int obstacles[10000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            obstacles[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(obstacles, n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops where outer loop runs n times and inner loop runs up to n times

⚠ Quadratic Growth

Space Complexity

O(n)

DP array to store longest sequence length ending at each position

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler