LESSON 328 OF 343 · GREEDY

Find Second Largest in C++: 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

C++ · GREEDY

Find Second Largest in C++, explained

Problem overview

The method secondLargest receives a vector of integers, nums, and returns its second largest value. Duplicates of the maximum do not count as a second place: in [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, which appears three times, and the answer is 8. The array is guaranteed to contain at least two distinct values, so an answer always exists.

Approach: track two numbers while scanning

The obvious solution sorts the vector in descending order and then walks past the copies of the maximum until it finds a smaller value. That costs O(n log n). The follow-up asks for one pass without sorting, and it is possible because you only ever need to remember two numbers: the largest so far and the largest value below it.

Keep two variables, maxVal and second. For every number in the vector there are three cases:

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

Here is the example traced. Both variables start at the smallest int, written -inf here.

num   maxVal   second
 2       2     -inf
 7       7       2
11      11       7
 8      11       8
11      11       8   (equal to max: ignored)
 8      11       8   (equal to second: ignored)
 3      11       8
11      11       8

It helps to see why the middle case needs both conditions. A runner-up must be a different value from the maximum, so a number equal to maxVal can't qualify, and it must beat the current runner-up to be worth recording. Because the three cases cover every possible number, no element is left in doubt.

A different one-pass idea is to find the maximum first, then scan again for the largest value that is not equal to it. That is two passes and still O(n). Tracking both values together does the job in a single loop, which is what the follow-up asks for.

Step by step

Declare maxVal and second as ints, both set to INT_MIN. Any real element is at least that large, so the first element always wins the comparison. This avoids a special "first iteration" check.
Loop over nums with a range-based for and an int named num.
Test for a new maximum: num > maxVal.
Demote, then replace. Inside that branch, copy maxVal into second first and only then assign num to maxVal. Reversing the two lines loses the old maximum.
Test for a new runner-up in an else if: num < maxVal && num > second. The first condition keeps copies of the maximum out of second place, and the second keeps small numbers from replacing a better runner-up.
Update second to num in that branch.
Return second after the loop.

The solution in C++

class Solution {
public:
    int secondLargest(vector<int>& nums) {
        int maxVal = INT_MIN;
        int second = INT_MIN;
        for (int num : nums) {
            if (num > maxVal) {
                second = maxVal;
                maxVal = num;
            } else if (num < maxVal && num > second) {
                second = num;
            }
        }
        return second;
    }
};

C++ details worth knowing:

INT_MIN is a macro for the smallest int, usually -2,147,483,648. It comes from <climits>. It is a safe starting point because no element can be smaller. Because the lesson guarantees two distinct values, second is always overwritten before the loop ends.
Loop by value. for (int num : nums) copies each int, which is as cheap as passing a reference. For bigger element types you would write const auto&.
The vector is taken by reference (vector<int>& nums), so calling the method does not copy the data, and this code never modifies it.
Chain of if and else if. At most one branch runs per element. When num > maxVal is true, the else if is skipped, which is why the demotion is done inside the first branch.

Complexity

Time: O(n). One pass over the vector, with a constant amount of work per element.

Space: O(1). Two integers, no matter how long the vector is. Sorting would add O(n log n) time, which this approach avoids.

Edge cases and common mistakes

Duplicates of the maximum. In [5, 5, 4] the answer is 4, not 5. The num < maxVal test in the second branch is what stops the second 5 from becoming second. If you wrote just num > second, the second 5 would be accepted when it arrives and the function would return 5.
Negative numbers. For [-5, -1, -9] the answer is -5. Starting the variables at 0 instead of INT_MIN would give 0, a value that is not in the vector.
Two elements. [1, 2] returns 1.
Increasing order. When the vector is already sorted ascending, every number is a new maximum, and the demotion step is the only thing that fills second.
The order of the two assignments in the first branch matters, as noted above.
Fewer than two distinct values. This case is excluded by the lesson. If it happened, say for [4, 4], the function would return INT_MIN, which can't be told from a real INT_MIN in the data.
INT_MIN as a real element. For [INT_MIN, 3] the function returns INT_MIN correctly, because 3 first becomes the maximum and demotes the old value.

Testing

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

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

Start learning free