Start learning free

LESSON 358 OF 415 · GREEDY

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

    SWIFT · GREEDY

    Find Second Largest in Swift, explained

    Problem overview

    The method secondLargest receives an array of integers, nums, and returns the second largest value. Duplicates of the maximum don't count as second place. In [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, which appears three times, so the answer is 8, not 11.

    The array always holds at least two distinct values. The follow-up asks for a solution that works in one pass without sorting.

    Approach: track the top two values

    Sorting the array and taking the second element from the end works, but it costs O(n log n) and still has to skip duplicates of the maximum. A single pass needs only two variables: the largest value seen so far and the largest value seen that is smaller than it.

    Each number 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 becomes the new runner-up.
    • Anything else, including a repeat of the maximum, changes nothing.

    Both variables start at Int.min, the smallest Int. Any real element beats that starting value, so the first iteration needs no special case.

    There are other ways. Sorting a copy in descending order and scanning for the first value different from the first element works, but it costs O(n log n). Two separate passes also work: one to find the maximum and one to find the largest value below it, which is O(n) but reads the array twice. The single pass below visits each element once, keeps the input untouched, and needs no extra array.

    The order of the two tests inside the loop is also part of the design. A value that beats the maximum is checked first, so the demotion happens before anything else can look at second. The second test only needs to handle values that are not new maximums.

    A worked trace

    Follow [2, 7, 11, 8, 11, 8, 3, 11], writing the pair as (maxVal, second) after each element and using -inf for Int.min:

    • 2 beats -inf: the pair becomes (2, -inf).
    • 7 beats 2: (7, 2).
    • 11 beats 7: (11, 7).
    • 8 is below 11 and above 7: (11, 8).
    • 11 equals the maximum, so neither test passes: (11, 8).
    • 8 is not above the runner-up 8: (11, 8).
    • 3 is below the runner-up: (11, 8).
    • The last 11 equals the maximum again: (11, 8).

    The function returns 8. Notice that the repeated 11 values never disturb the runner-up. That is the whole purpose of the strict comparison against maxVal.

    Step by step

    1. Declare maxVal and second as vars, both set to Int.min.
    2. Loop over nums with the loop variable num.
    3. Test whether num beats maxVal. A new maximum means the old one is demoted.
    4. Demote before replacing. Copy maxVal into second first, then store num in maxVal. Doing it the other way round would lose the old maximum.
    5. Add an else if for num < maxVal && num > second. The strict comparison with maxVal keeps duplicates of the maximum out of second place.
    6. Update second to num in that branch.
    7. Return second after the loop.

    The solution in Swift

    class Solution {
    func secondLargest(_ nums: [Int]) -> Int {
        var maxVal = Int.min
        var second = Int.min
        for num in nums {
            if num > maxVal {
                second = maxVal
                maxVal = num
            } else if num < maxVal && num > second {
                second = num
            }
        }
        return second
    }
}

    The Swift details worth a closer look:

    • Int.min is -9223372036854775808, since Int is 64 bits. Using it as a starting value is safe here because comparing never overflows.
    • else if chains. Only one branch runs per element. When num is a new maximum, the second condition isn't even tested.
    • Parameter labels. The underscore in _ nums means callers write secondLargest([1, 2]) without a label.
    • No parentheses needed. Swift conditions don't take parentheses, but braces are required around every body.

    Complexity

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

    Space: O(1). Only two extra variables.

    Edge cases and common mistakes

    • Duplicated maximum. [5, 5, 4] returns 4. Without the strict num < maxVal test, the second 5 would land in second.
    • Negative numbers. [-3, -1, -2] returns -2. Starting both variables at 0 instead of Int.min would wrongly return 0.
    • Two elements. [1, 2] returns 1.
    • Ascending order. [1, 2, 3, 4] returns 3: each new number pushes the old maximum down to second place.
    • Fewer than two distinct values. [5, 5] and [] both return Int.min, because second never changes. The lesson promises two distinct values, so this isn't tested.
    • Elements equal to Int.min. They look the same as the starting value. For [Int.min, 3] the function returns Int.min, which is correct, but it can't tell a real runner-up from "none found". An Int? variable avoids that ambiguity if you need it.

    Testing

    • [2, 7, 11, 8, 11, 8, 3, 11] gives 8.
    • [1, 2] gives 1.
    • [5, 5, 4] gives 4.
    • [-3, -1, -2] gives -2.
    • [1, 2, 3, 4] gives 3.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free