Problem overview
The method secondLargest receives an array of integers nums and returns its second largest value. Duplicates count once: in [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, which appears three times, and the second largest value is 8, not 11. The statement guarantees at least two distinct values, so an answer always exists.
Approach: sort, then find the first different value
If the array is sorted from largest to smallest, the maximum is at the front, and every copy of it sits together at the start. The second largest value is the first element that differs from the maximum. For the example the sorted array is [11, 11, 11, 8, 8, 7, 3, 2], and scanning from the left, the first value that isn't 11 is 8.
This takes O(n log n) time because of the sort. It is easy to get right, and it handles duplicates without any special code. The statement's follow-up asks about a single pass without sorting. That is O(n) and means tracking the two largest values seen so far. This lesson takes the simpler sorting route.
Step by step
- Sort in descending order. Call
sortonnumswith the comparator(a, b) => b - a. A negative result meansagoes first, so subtracting in this order puts bigger numbers first. Without a comparator,sortcompares elements as strings and would put 10 before 9. - Walk through the sorted array with
for...of, naming the loop variablenumand declaring it withconst. You need only the values here, not their positions. - Compare with the maximum. After sorting,
nums[0]is the largest value. Anifchecks whethernumis different from it. The values equal to the maximum fail the test and are skipped. - Return that value. The first
numthat passes the test is the second largest value. Because the input always has two distinct values, the loop returns before it ends.
The solution in JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
secondLargest(nums) {
nums.sort((a, b) => b - a);
for (const num of nums) {
if (num !== nums[0]) {
return num;
}
}
}
}
The JavaScript details worth a look:
- The numeric comparator.
[10, 9, 1].sort()gives[1, 10, 9], because"10"comes before"9"as text.(a, b) => b - acompares as numbers and sorts largest first. sortmodifies the argument. After the call, the caller's array is reordered. Sort a copy,[...nums].sort(...), if the original order still matters.!==. The strict comparison checks value and type. For numbers it simply means "not the same number".for...ofwithreturn. Areturninside the loop leaves the whole method at once. If the loop were ever to finish without returning, the method would give backundefined, which is what a JavaScript function returns when it reaches its end without areturnstatement.- Negative numbers. They need no special handling.
[-1, -5, -1]sorts to[-1, -1, -5]and the answer is -5.
Complexity
Time: O(n log n). The sort dominates. The scan that follows is at most one pass.
Space: O(1) extra as far as this code is concerned, since the array is sorted where it is and the loop uses one variable. The engine's sort may use working memory of its own.
Edge cases and common mistakes
- Returning
nums[1]. After sorting, that is the second element, which is the maximum again whenever the maximum is duplicated. In the example it gives 11, not 8. - Sorting without a comparator. For
[1, 10, 9]the default order is[1, 10, 9], sonums[0]is 1 and the first different value is 10. The method would return 10 instead of 9. - Only two values.
[1, 2]sorts to[2, 1]and the answer is 1. - All values equal.
[5, 5]is outside the guarantee. The loop never returns and the method gives backundefined. A real application would want to handle that case explicitly. - The input changes. If the caller reuses
numsafterwards, the sorted order may surprise them.
Testing
[2, 7, 11, 8, 11, 8, 3, 11]gives8.[1, 2]gives1.[-1, -5, -1]gives-5.[10, 9, 10]gives9.