The problem
Signals stand in a row, and a[i] is the height of signal i. For each signal, find the first signal to its right that is strictly taller, and give its height. If there is none, give -1. Return the answers as a new list.
next_greater([2, 7, 3, 5, 4, 6, 1]) # [7, -1, 5, 6, 6, -1, -1]
next_greater([3, 3, 3]) # [-1, -1, -1]
Limits
- Up to 200,000 signals. Your solution should be O(n).
Builds on STAQ-5 Monotonic stack.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
10 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The lesson's list | Not run | |
| 2 | Equal heights | Not run | |
| 3 | Going up | Not run | |
| 4 | Going down | Not run | |
| 5 | Empty | Not run | |
| 6 | One | Not run | |
| 7 | Answer far away | Not run | |
| 8 | Input not changed | Not run | |
| 9 | 200,000 going down | Not run | |
| 10 | 200,000 mixed | Not run |