Start learning free

LESSON 332 OF 347 · GREEDY

Find the Second Largest Value in C#: One Pass, No Sorting

Practice O(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 7
    Ctrl + Enter to check

    C# · GREEDY

    Find Second Largest in C#, explained

    Problem overview

    SecondLargest receives an array of integers and returns its second largest value. Duplicates of the maximum don't count as second place. For nums = [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. You may assume the array holds at least two distinct values.

    Approach: track two numbers while scanning

    The simplest solution sorts the array and walks back from the end until the value changes. That costs O(n log n). The follow-up asks for one pass without sorting, and two variables are enough: the largest value seen so far and the largest value seen that is smaller than it.

    Each number you meet falls into one of three cases:

    • It is bigger than the current maximum. The old maximum becomes the runner-up, and the number becomes the new maximum.
    • It is smaller than the maximum but bigger than the runner-up. It replaces the runner-up.
    • Otherwise it changes nothing. This includes numbers equal to the maximum, which is how duplicates of the top value stay out of second place.

    For comparison, a shorter version with LINQ (using System.Linq;) removes duplicates, sorts and skips the first value:

    int second = nums.Distinct().OrderByDescending(x => x).Skip(1).First();

    On the example array it also gives 8. It is easy to read, but it builds a new collection and sorts it, so it uses O(n) extra space and O(n log n) time. The loop below needs neither. It also ignores values that equal the maximum, whatever their position in the array, so the order of the input doesn't matter.

    Tracing the example: after 2 the pair is (max 2, second int.MinValue). 7 becomes the max and 2 the runner-up. 11 becomes the max and 7 the runner-up. 8 is below 11 and above 7, so it becomes the runner-up. The later 11s are equal to the max and are ignored, 8 is ignored because it equals the runner-up, and 3 is too small. The result is 8.

    Step by step

    1. Declare maxVal and second, both starting at int.MinValue. Any real element is at least that big, so the first element needs no special treatment.
    2. Loop over the array with foreach (int num in nums).
    3. Test whether num is greater than maxVal.
    4. Inside that branch, copy maxVal into second before overwriting maxVal. Done in the opposite order, the old maximum would be lost.
    5. Add an else if for values strictly below maxVal and strictly above second. The strict comparison with maxVal is what keeps a repeated maximum from becoming the runner-up.
    6. Assign num to second in that branch.
    7. Return second after the loop.

    The solution in C#

    class Solution {
    public int SecondLargest(int[] nums) {
        int maxVal = int.MinValue;
        int second = int.MinValue;
        foreach (int num in nums) {
            if (num > maxVal) {
                second = maxVal;
                maxVal = num;
            } else if (num < maxVal && num > second) {
                second = num;
            }
        }
        return second;
    }
}

    The two variables hold an invariant after every iteration: maxVal is the largest value in the prefix processed so far, and second is the largest value in that prefix that is strictly smaller than maxVal. Each branch exists to keep that statement true, and when the loop ends it describes the whole array.

    A few C# notes:

    • int.MinValue is the smallest int, -2147483648. It works as a "nothing yet" marker because no element can be smaller.
    • foreach reads each element in turn. It suits this loop because the code never needs the index and never writes to the array.
    • Because the branches are chained with else if, at most one of them runs for each element.

    Second largest versus second element

    The wording matters. "Second largest value" means the largest value that differs from the maximum. It is not the second element of the sorted array. In the example, sorted from the largest down, the array reads 11, 11, 11, 8, 8, 7, 3, 2. The second element is 11, but the second largest value is 8. The strict < in the second branch is what encodes this difference. If a task wanted the second element instead, that comparison would become <=.

    Complexity

    Time: O(n), since each element is examined once with a constant amount of work. Space: O(1), because only two extra integers are used.

    Edge cases and common mistakes

    • Duplicates of the maximum. For [5, 5, 4] the answer is 4. Using num <= maxVal in the second branch would let the second 5 become the runner-up.
    • Swapped assignments. Writing maxVal = num; before second = maxVal; makes both variables equal to the new maximum.
    • Negative numbers. [-3, -1, -2] gives -2. Starting both variables at 0 would break this, which is why the sentinel is int.MinValue.
    • Only one distinct value. [9, 9, 9] breaks the lesson's assumption, and the method returns int.MinValue, since the runner-up was never set. The input promise rules this case out.
    • Checking the second value first. If the order of the two branches is reversed, a number larger than the maximum can be treated as a runner-up.

    Testing

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