The runner-up
Find the second biggest different value in a list, in one pass. About 12 minutes.
No label this time
Think about a race. You can follow the whole race with just two boxes: one for the winner so far, one for the runner-up so far. When a new runner beats the winner, the old winner becomes the runner-up. When someone lands between the two, they take the runner-up spot.
A small hint for this one. Duplicates don't count twice: in a list where the biggest value appears two times, the second biggest is the next different value.
- x
- 4
- first
- 4
- second
- -1
Start with first and second both at -1, meaning nothing yet. 4 is bigger than first, so first is 4. The old first, -1, becomes second.
nums is [5, 5, 5]. Every value is the same. What should the second largest different value be?
- AThere isn't one, so the function returns -1
- B5
- C0
Show the answer
There isn't one, so the function returns -1. There is only one different value, so nothing can be the runner-up.
Second largest
Return the second largest different value in the list: the biggest value that is smaller than the maximum. If there are fewer than two different values, return -1.
nums = [4, 9, 2, 9, 7] → 7
0 ≤ length of nums ≤ 100,000 · 0 ≤ nums[i] ≤ 1,000,000