Biggest Value Ahead
EasyArrays & Hashing
Problem
A hiker has the elevations of the remaining waypoints in heights. For every waypoint they want to know the highest elevation still ahead of it (strictly to its right). The last waypoint has nothing ahead, so its answer is -1.
Return the array of answers.
Example 1
- Input:
- heights = [17, 18, 5, 4, 6, 1]
- Output:
- [18, 6, 6, 6, 1, -1]
Ahead of 17 the highest is 18; ahead of 18 it is 6; the last has nothing ahead.
Example 2
- Input:
- heights = [400]
- Output:
- [-1]
Constraints
- 1 ≤ heights.length ≤ 10^4
- 1 ≤ heights[i] ≤ 10^5
Hint
Show the first hint
Computing the maximum of the right part from scratch for each index repeats a lot of work.
Walkthrough
How to approach it
01Clarify before coding
- Strictly to the right? Yes, the element itself is not included.
- What for the last element? -1.
- Can values repeat? Yes; an equal value ahead still counts as the maximum.
02Brute force
For each i, scan i + 1..n-1 and take the maximum.
Cost: O(n²) time: about 5 · 10^7 comparisons at n = 10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.