249. Second Largest
Foundation1000 ms256 MBSolved by 0%
Print the second largest DISTINCT value among n integers. If every value
is the same, print None.
Distinct matters. In 5 5 4 the answer is 4, not 5, because the two fives are
one distinct value.
You can sort and walk backwards, which is O(n log n). You can also do it in
one pass with two variables, which is O(n) and is the version worth being
able to write: it is the same idea as finding a maximum, with a second slot.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print the second largest distinct value, or None if there is no second distinct value.
Input5
3 1 4 1 5
Output4
Notehas its answer next to the largest value
Input1
1
OutputNone
Noteis a single element, so there is no second distinct value
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.