Start learning free

LESSON 229 OF 415 · SORTING

Find Second Largest in Swift: Sort and Scan from the Back

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

    SWIFT · SORTING

    Find Second Largest in Swift, explained

    Problem overview

    The method secondLargest receives an array of integers and returns the second largest value. "Value" matters: if the maximum appears several times, the copies don't count as the second largest. The array is guaranteed to contain at least two different values.

    In [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, which appears three times. The next distinct value below it is 8, so the answer is 8. Returning the second element of a descending sort would give 11 instead, and that is the trap.

    Approach: sort, then skip the maximum

    If the array is sorted in ascending order, the maximum is the last element. The second largest value is the first element, scanning from the back, that differs from the maximum. Everything equal to the maximum is a duplicate and is skipped.

    For the example, the sorted array is [2, 3, 7, 8, 8, 11, 11, 11]. The last element is 11. Walking backwards from the second-to-last position: 11, then 11, then 8. The first value that isn't 11 is 8, so that is the answer.

    Sorting costs O(n log n). A single pass that tracks the two largest values seen so far would be O(n); this lesson takes the simpler sorted version first.

    Step by step

    1. Sort into a new array. The parameter is a constant, so nums.sorted() gives an ascending copy, stored in a constant named sorted.
    2. Walk backwards. Swift has no C-style for loop, so a backwards loop uses stride(from:through:by:). Here it starts at sorted.count - 2, the position just before the maximum, goes down to 0 inclusive, and steps by -1.
    3. Compare with the maximum. Inside the loop, test whether sorted[i] differs from sorted[sorted.count - 1]. Elements equal to it are copies of the maximum.
    4. Return the first different value. Since the array is sorted, it is the largest value below the maximum.
    5. Add a fallback return of -1. The guarantee of two distinct values means it is never reached, but Swift requires every path of a function to return.

    The solution in Swift

    class Solution {
    func secondLargest(_ nums: [Int]) -> Int {
        let sorted = nums.sorted()
        for i in stride(from: sorted.count - 2, through: 0, by: -1) {
            if sorted[i] != sorted[sorted.count - 1] {
                return sorted[i]
            }
        }
        return -1
    }
}

    The Swift details worth knowing:

    • stride with through: and to:. stride(from: a, through: b, by: s) includes b, while stride(from: a, to: b, by: s) stops before it. Here through: 0 makes sure index 0 is checked. With to: 0 the first element would be skipped.
    • Reversed ranges don't exist. A range like 5..<0 is not valid and crashes at run time. To count down, use stride or reverse a forward range with .reversed().
    • A local named sorted. The constant has the same name as the array method sorted(). They don't clash, because the method is always called on an array as nums.sorted() and the constant is an array of its own.
    • Returning from inside a loop. return leaves the whole function at once, so the loop stops at the first match.
    • The final return -1. Without it the compiler reports that the function is missing a return in some paths.

    A one-pass version

    The follow-up idea is to skip the sort. Keep the largest and the second largest value seen so far and update them in a single loop:

    func secondLargestOnePass(_ nums: [Int]) -> Int {
    var largest = Int.min
    var second = Int.min
    for x in nums {
        if x > largest {
            second = largest
            largest = x
        } else if x < largest && x > second {
            second = x
        }
    }
    return second
}

    A new maximum pushes the old maximum down to second place. A value strictly between the two becomes the new second. A value equal to the maximum is ignored, which handles duplicates. This runs in O(n) time and O(1) space. It returns the same answers as the lesson's version, for example 8 for the example above.

    Complexity

    Time: O(n log n). Sorting dominates. The backward scan stops at the first value below the maximum and, in the worst case, visits all n - 1 earlier positions when the maximum is repeated many times, so it is O(n).

    Space: O(n). sorted() allocates a second array of n elements.

    Edge cases and common mistakes

    • Repeated maximum. [5, 5, 3] returns 3. Taking sorted[count - 2] would return 5.
    • Two elements. [1, 2] returns 1: the loop starts at index 0 and finds 1 differs from 2.
    • Negative numbers. [-1, -5, -1] returns -5. Nothing in the logic depends on the sign.
    • Using to: instead of through:. The loop would never check index 0, so [1, 2] would fall through to the fallback and return -1.
    • Starting at sorted.count - 1. The maximum would be compared with itself and always skipped, which wastes a step but is harmless. Starting at sorted.count reads past the end and crashes.
    • Using Int.min as a starting value in the one-pass version. This works for the guaranteed input, but if the array could hold Int.min itself, the initial values would be confused with real data.

    Testing

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