Start learning free

LESSON 200 OF 343 · SORTING

Find Second Largest in C++: Sort in Descending Order, O(n log n)

Practice O(n log n) Read the full explanation

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 5
    Ctrl + Enter to check

    C++ · SORTING

    Find Second Largest in C++, explained

    Problem overview

    The function secondLargest receives a vector of integers, nums, and returns the second largest value. Duplicates don't count as separate ranks. In [2, 7, 11, 8, 11, 8, 3, 11] the largest value is 11, which appears three times, and the second largest value is 8, not 11. The problem guarantees at least two distinct values, so an answer always exists.

    Approach: sort, then skip the maximum

    If the numbers are sorted from largest to smallest, the maximum is at the front, and equal values are next to each other. The second largest value is the first element that differs from the maximum. Scanning from the front and returning the first different value handles any number of copies of the maximum.

    For the example, descending order is [11, 11, 11, 8, 8, 7, 3, 2]. The scan skips the three 11s and returns the first 8.

    Sorting costs O(n log n), which is more than necessary. The statement's follow-up asks for a single pass without sorting: keep the largest and second largest values seen so far and update them as you go. This lesson takes the simpler route, which is easier to get right, and the idea of "skip the duplicates of the maximum" is the same.

    Step by step

    1. Sort in descending order. Call sort with the range nums.begin() to nums.end() and the comparator greater<int>(). The default order is ascending, and greater<int> reverses it. The sort works in place.
    2. Loop over the values with a range-based for, using an int variable num.
    3. Compare with the maximum. After sorting, nums[0] is the largest value. Test whether num differs from it.
    4. Return the first different value. Because the vector is sorted, that value is the next one down, the second largest.
    5. Add a fallback return of -1. If every element equals the maximum, the loop would end without returning. The problem rules that out, so the line never runs. It is there because a function with a return type must return on every path, and a missing return is undefined behaviour in C++.

    The solution in C++

    class Solution {
public:
    int secondLargest(vector<int>& nums) {
        sort(nums.begin(), nums.end(), greater<int>());
        for (int num : nums) {
            if (num != nums[0]) {
                return num;
            }
        }
        return -1;
    }
};

    The C++ details worth knowing:

    • sort takes an iterator range. nums.begin() points at the first element and nums.end() points one past the last. The third argument is an optional comparison object.
    • greater<int>() is a function object. It lives in the <functional> header and answers "is the first argument greater than the second?". With it, sort puts larger values first. An alternative is to sort ascending and read from the back, or to use nums.rbegin() and nums.rend().
    • The input is modified. The parameter is vector<int>&, a reference, so the caller's vector ends up sorted. That avoids a copy but has a side effect. If the caller needs the original order, copy the vector first or take it by value.
    • Range-based for copies each value. int num is a copy of the element, which is cheap for an int.
    • Reading nums[0] repeatedly. This is fine, since the vector is not empty when the loop body runs. The vector is never changed during the loop.

    Complexity

    Time: O(n log n). The sort dominates. The scan afterwards is O(n) in the worst case, when the second largest value is at the very end.

    Space: O(log n), typically. The sort works in place on the vector. Common implementations use a small amount of stack space for the recursion, but the standard doesn't promise an exact bound, so it is safest to say that no extra array of size n is created.

    Edge cases and common mistakes

    • Returning nums[1] after sorting. That is the second largest element, not value. For [11, 11, 8] it would return 11, but the answer is 8.
    • Two elements. [1, 2] becomes [2, 1] and the function returns 1.
    • Negative numbers. [-1, -5, -3] becomes [-1, -3, -5] and the function returns -3. Nothing in the approach depends on the sign. A one-pass version that starts its maximum at 0 would get this wrong.
    • Several copies of the maximum at the front. [5, 5, 4] gives 4. This is why the comparison is against nums[0] and not against the previous element.
    • Sorting ascending and returning the second element from the end. That has the same duplicate trap as nums[1]. Scan for the first value that differs from the end.
    • Dropping the fallback return. The code may still compile, with a warning, but control reaching the end of a non-void function is undefined behaviour.

    Testing

    • [2, 7, 11, 8, 11, 8, 3, 11] gives 8.
    • [1, 2] gives 1.
    • [5, 5, 4] gives 4.
    • [-1, -5, -3] gives -3.
    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