Funcia
Lv.1array

Buildings with a Sea View

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Buildings stand in a row with the sea beyond the right end; heights lists their heights from left to right. A building has a sea view if every building to its right is strictly lower. Return the indices (0-based) of the buildings with a sea view in increasing order.

Examples

heightsresult
[4, 2, 3, 1][0, 2, 3]
[1, 3, 2, 4][3]
[5, 5, 5][2]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(heights: int[]) → int[]

Constraints

  • 1≤1 \le heights.length ≤200,000\le 200{,}000
  • 1≤1 \le heights[i] ≤109\le 10^9

Expected complexity

Time
O(N)
Space
O(1) extra

Examples

heightsExpected
[4,2,3,1][0,2,3]
[1,3,2,4][3]
[5,5,5][2]

Hint

Hint

"All buildings to the right are lower" means "taller than the maximum to the right". Scan from the right end keeping the running maximum, collect the indices that beat it, and reverse at the end. Checking every building to the right is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251350 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.