LESSON 333 OF 348 · GREEDY

Find Second Largest in TypeScript: One Pass Without 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

TYPESCRIPT · GREEDY

Find Second Largest in TypeScript, explained

Problem overview

The method secondLargest receives an array of numbers, nums, and returns the second largest value. The word "value" matters: duplicates of the maximum don't count as the runner-up. The array is guaranteed to hold at least two distinct values.

In the example, nums = [2, 7, 11, 8, 11, 8, 3, 11]. The maximum is 11, and it appears three times. The largest value that is different from 11 is 8, so the answer is 8, not 11.

The follow-up asks for one pass and no sorting, which is what this lesson does.

Approach: keep two trackers

The simplest solution sorts the array in descending order and looks for the first value that differs from the first element. That costs O(n log n), and it reorders the array unless you copy it first.

A single pass does better. Keep two variables as you scan: maxVal, the largest value seen so far, and second, the largest value seen so far that is smaller than maxVal. For each number there are three cases:

It is bigger than maxVal. It becomes the new maximum, and the old maximum becomes the runner-up.
It is smaller than maxVal but bigger than second. It is a better runner-up.
Anything else, including a number equal to maxVal, changes nothing.

Both variables start at -Infinity, which is smaller than every real number. That removes the need for a special "first element" check: the first number always beats maxVal.

On the example, the trackers change like this:

num	maxVal	second
2	2	-Infinity
7	7	2
11	11	7
8	11	8
11	11	8
8	11	8
3	11	8
11	11	8

The repeated 11s are ignored because they are not strictly less than maxVal, and they are not greater than it either.

Why this beats the alternatives

There are two other common ways to solve it. The first is to sort a copy of the array in descending order and scan for the first value that differs from the front. It is correct, but it does O(n log n) work to find something a single scan can find, and it needs a copy to avoid reordering the caller's array.

The second takes two passes: find the maximum, then find the largest value that is not equal to it. That is also O(n), and it is a fine solution. The one-pass version simply folds both searches into one loop, which is why it has to be careful about the order of its updates. The trackers must be updated so that second is always the best candidate strictly below maxVal, at every moment, not only at the end.

Step by step

Declare both trackers with let, starting at -Infinity. They change during the loop, so const won't do.
Loop over nums with for...of, declaring each element as const num. You only read the value; you don't need its index.
Test num > maxVal first. A new maximum pushes the old one down to second place.
Copy before overwriting. Inside that branch, assign second = maxVal first and then maxVal = num. In the other order, the old maximum is lost.
Add an else if for num < maxVal && num > second. The strict < keeps a duplicate of the maximum from taking second place.
Assign second = num inside that branch.
Return second after the loop.

The solution in TypeScript

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

Language details worth knowing:

-Infinity is a number. In JavaScript and TypeScript, Infinity and -Infinity are ordinary values of type number and compare correctly with every finite number. That is why the variables are inferred as number without an annotation.
Negative numbers work. [-5, -1, -9] returns -5. Starting the trackers at 0 would break this, since every element would be smaller than the starting value.
The types vanish at run time. The annotations number[] and number are checked by the compiler and removed from the JavaScript it writes. If the array reaches the method with strings in it, nothing in the compiled code checks that.
else if is exclusive. A number that becomes the new maximum never reaches the second test.

Complexity

Time: O(n). One pass, with a few comparisons per element.

Space: O(1). Two variables, whatever the array's length.

Edge cases and common mistakes

Duplicates of the maximum. [1, 5, 5, 3] returns 3. If the second test were only num > second, a repeated 5 would be accepted as the runner-up and the method would return 5.
Ascending, descending and tiny inputs. [1, 2, 3], [3, 2, 1] and [5, 1] return 2, 2 and 1.
Overwriting in the wrong order. Writing maxVal = num; second = maxVal; makes both trackers equal to the new maximum.
Fewer than two distinct values. The lesson promises this never happens. If it did, second would stay at -Infinity: [5, 5], [7] and an empty array all return -Infinity.
Sorting without a comparator. sort() compares elements as strings, so [10, 9, 1].sort() gives [1, 10, 9]. A sort-based solution needs (a, b) => b - a.

Testing

[2, 7, 11, 8, 11, 8, 3, 11] gives 8.
[5, 1] gives 1.
[1, 5, 5, 3] gives 3.
[-5, -1, -9] gives -5.
[3, 2, 1] gives 2.

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

Start learning free