Problem overview
The method secondLargest receives an array of integers, nums, and returns the second largest value. The array is guaranteed to hold at least two distinct values.
The word "value" matters. In [2, 7, 11, 8, 11, 8, 3, 11], the largest value is 11, which appears three times. The second largest is 8, not 11: duplicates of the maximum don't count as a second place.
Approach: sort in descending order
After sorting from largest to smallest, the maximum is at index 0 and every copy of it sits in front. The second largest value is the first element that is different from the one at index 0. For the example, the sorted array is [11, 11, 11, 8, 8, 7, 3, 2], and the first value that isn't 11 is 8.
Sorting costs O(n log n). The statement mentions a follow-up: solving it in one pass without sorting, by tracking the largest and second largest values as you scan. That runs in O(n). This lesson takes the simpler route, which is easier to reason about, and the one-pass version is worth trying afterwards.
Step by step
- Sort
numsin descending order in place, using the comparator(a, b) => b - a. A positive result putsbfirst, so larger numbers come first. Without a comparator, the numbers would be compared as strings. - Loop over
numswithfor...of, declaring the loop variablenumwithconst, to scan from left to right. - Compare each
numwithnums[0]in anif. Values equal to the maximum are duplicates of the largest and must be skipped. - Return the first
numthat differs. The array is in descending order, so it is the next smaller value, and that is the second largest. The guarantee of two distinct values means the loop always reaches such an element.
The solution in TypeScript
class Solution {
secondLargest(nums: number[]): number {
nums.sort((a, b) => b - a);
for (const num of nums) {
if (num !== nums[0]) {
return num;
}
}
}
}
Details worth knowing:
for...ofgives you the values themselves, not the indices. It reads cleanly when you don't need the position. Useconstfor the loop variable when you don't reassign it.- No return after the loop. The loop is left through the
returninside it, and the lesson's guarantee means the loop never ends without returning. With the lessons' compiler flags, tsc doesn't report the missing final return. If the guarantee were broken, for example for[5, 5], the method would finish without returning and the caller would receiveundefined, even though the declared type isnumber. !==compares two numbers without converting types.- Sorting changes the input. The caller's array ends up in descending order. Use
[...nums].sort(...)to keep the original.
Complexity
Time: O(n log n). The sort dominates. The loop makes at most one pass, and it stops early at the first value below the maximum.
Space: O(1). The sort works in place, and the loop adds only its variable.
Edge cases and common mistakes
- Duplicates of the maximum. Returning
nums[1]after sorting is wrong whenever the maximum appears more than once: for the example it would return 11. - Two elements.
[1, 2]returns 1. - Negative numbers.
[-5, -1, -1]returns -5. Nothing in the approach assumes positive values. - Forgetting the comparator or its direction. Without a comparator,
[1, 10, 2]is ordered as strings and stays[1, 10, 2], so the method returns 10 instead of 2. With(a, b) => a - b, the maximum is at the end of the array, not at index 0. - Only one distinct value.
[5, 5]breaks the guarantee, and the method returnsundefined. It isn't a valid input here.
Testing
[2, 7, 11, 8, 11, 8, 3, 11]gives8.[1, 2]gives1.[-5, -1, -1]gives-5.[100, 20, 3]gives20.