LESSON 329 OF 344 · GREEDY

Find Second Largest in JavaScript: One Pass, No Sorting

Given an array of integers, return the second largest value.

Example:

Input: nums = [2, 7, 11, 8, 11, 8, 3, 11]
Output: 8
Explanation: The maximum value is 11. The second largest value is 8.

Note:

You may assume the array contains at least two distinct values.

Follow up:

Could you solve this in one pass without sorting?

STEP 1 OF 7

Guided

Ctrl + Enter to check

JAVASCRIPT · GREEDY

Find Second Largest in JavaScript, explained

Problem overview

The method secondLargest receives an array of integers, nums, and returns its second largest value. The wording matters: duplicates of the maximum do not count as the runner-up. The array is guaranteed to contain at least two distinct values, so an answer always exists.

For [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, which appears three times. The second largest value is 8, not 11, because 11 is already the largest. The follow-up asks for a solution that makes one pass over the array without sorting.

Approach: track the two best values as you scan

The simple idea is to sort the array in descending order and pick the first value different from the first element. That works, but sorting costs O(n log n), and it needs a custom comparator in JavaScript, since nums.sort() with no comparator compares elements as strings. (For example, [10, 9, 1].sort() gives [1, 10, 9].) Sorting also reorders the caller's array.

A single pass is enough. Keep two variables: max, the largest value seen so far, and second, the largest value seen so far that is strictly smaller than max. For each number there are three possibilities:

It is bigger than max. The old maximum is now the best value below the new one, so it becomes second, and the number becomes max.
It is smaller than max but bigger than second. It is a better runner-up.
Anything else changes nothing: either it equals max, which is a duplicate and not a new value, or it is no better than the current second.

Both variables start at -Infinity. Every real number in the array is greater than -Infinity, so the first element always replaces max, and there is no need for a special "first iteration" case.

Step by step

Declare max and second with let, both set to -Infinity. They must be let since they change.
Loop over nums with for (const num of nums). A new constant per iteration is enough because the loop never changes num.
Check whether num > max. This is the case where a new champion appears.
In that branch, move the old maximum down first. Assign second = max and only then max = num. In the opposite order, the old maximum is lost and second would receive the new value.
Add an else if for num < max && num > second. The first condition keeps a duplicate of the maximum out of second. The second keeps a smaller number from replacing a better runner-up.
Assign second = num inside it.
Return second after the loop.

Tracing [2, 7, 11, 8, 11, 8, 3, 11], the pair (max, second) goes: start (-Infinity, -Infinity); after 2 it is (2, -Infinity); after 7, (7, 2); after 11, (11, 7); after 8, (11, 8). The remaining 11, 8, 3 and 11 change nothing, because 11 equals the maximum and 8 and 3 are not larger than 8. The answer is 8.

The solution in JavaScript

class Solution {
    secondLargest(nums) {
        let max = -Infinity;
        let second = -Infinity;
        for (const num of nums) {
            if (num > max) {
                second = max;
                max = num;
            } else if (num < max && num > second) {
                second = num;
            }
        }
        return second;
    }
}

JavaScript details worth knowing:

-Infinity is a real value of the number type, smaller than every other number, including negative ones. It makes an array such as [-5, -1] work without special handling. Starting both variables at 0 instead would give wrong answers for negative inputs.
let and const. let allows reassignment. for (const num of nums) is allowed because each iteration creates a fresh binding.
for...of reads values. for...in gives indexes as strings, which is a common source of bugs when looping over arrays.
The array is not changed. Unlike a sort-based solution, this one only reads nums.
Comparison operators on numbers work as expected. Mixing in strings would not be safe, for instance "10" > "9" is false because strings compare character by character, but the lesson's input holds only numbers.

Complexity

Time: O(n). The loop visits each element once and does a constant amount of work for it. A sort-based solution takes O(n log n).

Space: O(1). Two variables, no matter how long the array is.

Edge cases and common mistakes

Duplicates of the maximum. For [5, 5, 4] the answer is 4. Without the num < max test, the second 5 would be copied into second and the function would return 5.
Negative numbers. [-1, -5] returns -5. The -Infinity starting value handles this where a starting value of 0 would fail.
The maximum comes first or last. [11, 8] and [8, 11] both return 8: in the first case 8 is caught by the else if, in the second the maximum is demoted by the first branch.
Swapped assignments. Writing max = num; second = max; sets both to the new value, and the old maximum is lost.
Fewer than two distinct values. The lesson guarantees this never happens. If it did, for instance [3, 3], the function would return -Infinity, because second was never updated.
Using else instead of else if with a condition. A plain else would put values equal to the maximum, and values below the runner-up, into second.

Testing

[2, 7, 11, 8, 11, 8, 3, 11] gives 8.
[5, 5, 4] gives 4.
[-1, -5] gives -5.
[1, 2] gives 1.
[1, 1] breaks the lesson's guarantee and gives -Infinity.

Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free