Longest Mountain Run
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
A contiguous segment of heights is a mountain if its length is at least 3 and there is a peak index p, neither the first
nor the last of the segment, such that the values strictly increase up to p and strictly decrease after it.
Return the length of the longest mountain, or 0 if there is none.
Examples
| heights | result |
|---|---|
[2, 1, 4, 7, 3, 2, 5] | 5 |
[2, 2, 2] | 0 |
[1, 3, 2, 4, 6, 5, 1] | 5 |
Example 1 — [1, 4, 7, 3, 2].
Example 2 — Flat, so no mountain.
Example 3 — Mountains [1, 3, 2] and [2, 4, 6, 5, 1] share the valley 2; the longer has length 5.
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
-
heights.length -
heights[i]
Expected complexity
- Time
- O(N)
- Space
- O(N)
Examples
| heights | Expected |
|---|---|
[2,1,4,7,3,2,5] | 5 |
[2,2,2] | 0 |
[1,3,2,4,6,5,1] | 5 |
Hint
Hint
Precompute up[i] (how many strictly increasing steps end at i) from the left and down[i] (how many strictly decreasing
steps start at i) from the right. Any i with both positive is a peak of a mountain of length up[i] + down[i] + 1. That is
; extending from every start is on one huge mountain.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1100 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 13 | verdict only |
| performance | 60 | 4 | verdict only |