Problem overview
The method secondLargest receives a list of integers nums and returns the second largest value. The word value matters: duplicates of the maximum don't count as the second largest. The statement promises at least two distinct values, so an answer always exists.
For [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, and it appears three times. The second largest value is 8, not 11. The answer is 8.
Approach: sort in descending order
If the list is sorted from largest to smallest, the maximum sits at index 0. The second largest value is the first element that differs from it. The list above becomes [11, 11, 11, 8, 8, 7, 3, 2]. Walking from the left, the elements 11, 11 and 11 are equal to the maximum and are skipped. The first different one is 8.
Simply returning nums[1] would be wrong, since it would give 11 here. Duplicates of the maximum are exactly why the loop is needed.
Sorting takes O(n log n) time. The statement also mentions a follow-up, a single pass without sorting; this lesson takes the sorting route because it is simple to reason about, and the single pass is described below.
Step by step
- Sort in descending order. Call
nums.sort(reverse=True). The largest values move to the front. - Walk through the list with a loop variable named
num, from left to right. - Compare each value with the maximum. The test is
num != nums[0]. While the values equal the maximum, nothing happens. - Return the first value that differs. Everything after the maximum copies is smaller, so this is the second largest value. The guarantee of two distinct values means the loop always returns before it runs out of elements.
The solution in Python
class Solution:
def secondLargest(self, nums: List[int]) -> int:
nums.sort(reverse=True)
for num in nums:
if num != nums[0]:
return num
Python details to notice:
sort(reverse=True)sorts in place from largest to smallest. It returnsNone, so it is written as a statement and not assigned to anything.sorted(nums, reverse=True)would return a new list instead.- The input list changes. After the call, the caller's list is in descending order. Use
sortedon a copy if the original order matters. - No final
return. If the loop ended without returning, the method would returnNone, which is Python's result for a function that finishes without areturn. With valid input that can't happen. nums[0]is re-read each pass. It is fixed after the sort, so the comparison is always against the same maximum.- Negative numbers need no special care. Sorting handles them, and
[-3, -3, -7]gives-7.
The one-pass follow-up
The follow-up asks for O(n) time. Keep the largest and the second largest seen so far, and update both as you scan:
def second_largest(nums):
first = second = None
for x in nums:
if first is None or x > first:
first, second = x, first
elif x != first and (second is None or x > second):
second = x
return second
A new maximum pushes the old maximum down to second place. Otherwise, a value that isn't equal to the maximum can replace the second place if it is larger. The check x != first keeps duplicates of the maximum out of the second place. On the example list this returns 8. It never sorts, so it uses constant extra space.
Complexity
Time: O(n log n). The sort dominates. The loop walks at most n elements and costs O(n).
Space: O(1) extra for the loop. Python's sort works on the list itself, though it may use temporary memory internally.
Edge cases and common mistakes
- Returning
nums[1]. It fails whenever the maximum is repeated, as in the example. - Using a set.
sorted(set(nums))[-2]also works, but it builds extra collections, and it must pick index-2, not-1. - Two elements.
[1, 2]gives 1. - All but one equal.
[5, 5, -1]gives -1. - Sorting ascending by mistake. Without
reverse=True, the maximum is at the end andnums[0]is the minimum, so the loop would return the second smallest value. - Inputs with one distinct value.
[1, 1]breaks the promise. The method would returnNone.
Testing
[2, 7, 11, 8, 11, 8, 3, 11]gives8.[1, 2]gives1.[5, 5, -1]gives-1.[-3, -3, -7]gives-7.