Second Largest Number
You get a list of integers nums. Return its second largest distinct value: the largest value that is strictly smaller than the maximum. Values can repeat, so for [5, 5, 3] the answer is 3, not 5. The list always holds at least two different values.
Function
- numsinteger-array
- the list of integers, with at least two distinct values
- Returnsinteger
- the largest value that is smaller than the maximum
Constraints
2 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numscontains at least two distinct values.
Examples
- Input
- nums = [4, 9, 2, 7, 9]
- Output
- 7
- Explanation
- The maximum is
9. It appears twice, but a second copy of the maximum does not count, so the answer is the next value down,7.
- Input
- nums = [-5, -1, -8]
- Output
- -5
- Explanation
- From largest to smallest the values are
-1,-5,-8, so the second largest is-5.
- Input
- nums = [6, 6, 6, 3]
- Output
- 3
- Explanation
- Only two distinct values exist,
6and3. However many times6repeats, the second largest is3.
Follow-up
Can you return the third largest distinct value in one pass, with three variables and no sorting?
Hints
Open them one at a time. Each one gives away a little more.
Finding the maximum takes one variable. What would a second variable let you remember as you read the list?
Track the largest and the second largest distinct values. A new value can beat the largest, land strictly between the two, or change nothing.
Start both variables below every allowed value. If
x > largest, shiftlargestintosecondand storex. Otherwise, ifxis strictly between them, store it insecond.
Solution
The maximum can repeat, and a repeat must not count as the second largest. The answer can be negative, so a variable that starts at 0 fails on an all-negative list. One pass that tracks the top two distinct values with strict comparisons handles both.
Sort and step down past the maximum
Intuition
Sort a copy and walk left from the end past every copy of the maximum; the first different value is the answer. For [6, 6, 6, 3] you skip three 6s and land on 3. The walk cannot run off the front, because the list holds two distinct values.
Sorting orders every value when you need only the top two: O(n log n) time, plus O(n) memory for the copy.
Algorithm
- Copy
numsand sort the copy from smallest to largest. - Start an index
iat the last position. - While the value at
iequals the maximum, moveione step left. - Return the value at
i.
def secondLargest(nums):
ordered = sorted(nums)
i = len(ordered) - 1
# Step left past every copy of the maximum.
while ordered[i] == ordered[-1]:
i -= 1
return ordered[i]Two passes
Intuition
The first pass finds the maximum. The second keeps the largest value strictly smaller than it. For [4, 9, 2, 7, 9] the first pass finds 9, and the second skips both 9s and keeps 7.
Start second below every allowed value. Some value is smaller than the maximum, so that start always gets replaced. Each pass is a running maximum: O(n) time and O(1) space. Reading the list twice is the cost, and a stream of values you see once does not allow it.
Algorithm
- Loop over
numsonce and store the maximum inlargest. - Set
secondbelow every allowed value. - Loop again. For each
xwithx < largestandx > second, setsecondtox. - Return
second.
def secondLargest(nums):
largest = nums[0]
for x in nums:
if x > largest:
largest = x
second = float("-inf") # below every allowed value
for x in nums:
if x < largest and x > second:
second = x
return secondOne pass tracking the top two
Intuition
Keep largest and second, the top two distinct values so far. A value bigger than largest pushes the old largest down to second. A value strictly between second and largest replaces second. Anything else, including another copy of largest, changes nothing: the strict comparisons skip duplicates.
For [4, 9, 2, 7, 9], largest goes 4, then 9 with second = 4. 7 lies between them, so second = 7, and the last 9 is skipped. Start both variables below every possible value, since the answer can be negative. Two distinct values guarantee that second ends on a value from the list.
Algorithm
- Set
largestandsecondbelow every allowed value. - Loop over every value
xinnums. - If
x > largest, movelargestintosecondand setlargesttox. - Otherwise, if
x < largestandx > second, setsecondtox. - After the loop, return
second.
def secondLargest(nums):
# Both start below every allowed value.
largest = second = float("-inf")
for x in nums:
if x > largest:
second = largest # the old maximum drops to second place
largest = x
elif largest > x > second:
second = x
return second
Pitfalls and edge cases
- Returning the second to last element of the sorted list. With a repeated maximum, as in
[4, 9, 2, 7, 9], that is the maximum again. - Starting the variables at
0. On[-5, -1, -8]no value beats0, and you return0, which is not in the list. - Writing
x >= largestin the first case. A second9then pushes the first9intosecond, and you return9. - Updating
secondonly when a new maximum appears. In[10, 20, 15], the15never reachessecond, and you return10.
Frequently asked questions3
What is the time complexity of finding the second largest element?
The one-pass and two-pass methods both take O(n) time and O(1) extra space; sorting first takes O(n log n). You cannot beat O(n), because every value has to be read once.
How do duplicates affect the second largest element?
This problem asks for the second largest distinct value, so copies of the maximum are skipped: [9, 9, 7] gives 7. Some versions count positions instead and answer 9, so check which one is meant before you code.
What should you return when there is no second largest value?
Here it cannot happen, because the list holds two distinct values. In general, a list such as [4, 4, 4] has no answer: return a marker such as -1 or null, or raise an error. You detect it when second still holds its starting value after the loop.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def secondLargest(nums):
# Write code hereTest #1
Test #2
Test #3
Argument
nums = [4, 9, 2, 7, 9]
Expected Output
7