Tap here to switch tabs
Problem
Submissions

Problem: Find the Longest Valid Obstacle Course at Each Position

Find the Longest Valid Obstacle Course at Each Position in an integer array of obstacle heights, return an array with the longest nondecreasing course ending at every position and including that obstacle.

Statement

You are given a 00 indexed integer array obstacles of length n, where obstacles[i] represents the height of the ithi^{ {th}} obstacle.

For every index i from 00 to n - 1, determine the length of the longest obstacle course that ends at index i satisfying the following conditions:

  • You select a sequence of obstacles with indices between 00 and i, inclusive.

  • You must include the ithi^{ {th}} obstacle in the chosen course.

  • The relative order of the selected obstacles must match their original order in obstacles.

  • The height of each chosen obstacle must be greater than or equal to the height of the preceding chosen obstacle.

Return an integer array ans of length n, where ans[i] is the maximum length of a valid obstacle course ending at index i.

Constraints:

  • n == obstacles.length

  • 1≤1 \leq n ≤105\leq 10^5

  • 1≤1 \leq obstacles[i] ≤107\leq 10^7

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Find the Longest Valid Obstacle Course at Each Position

Find the Longest Valid Obstacle Course at Each Position in an integer array of obstacle heights, return an array with the longest nondecreasing course ending at every position and including that obstacle.

Statement

You are given a 00 indexed integer array obstacles of length n, where obstacles[i] represents the height of the ithi^{ {th}} obstacle.

For every index i from 00 to n - 1, determine the length of the longest obstacle course that ends at index i satisfying the following conditions:

  • You select a sequence of obstacles with indices between 00 and i, inclusive.

  • You must include the ithi^{ {th}} obstacle in the chosen course.

  • The relative order of the selected obstacles must match their original order in obstacles.

  • The height of each chosen obstacle must be greater than or equal to the height of the preceding chosen obstacle.

Return an integer array ans of length n, where ans[i] is the maximum length of a valid obstacle course ending at index i.

Constraints:

  • n == obstacles.length

  • 1≤1 \leq n ≤105\leq 10^5

  • 1≤1 \leq obstacles[i] ≤107\leq 10^7