Start learning free

LESSON 205 OF 348 · SORTING

Find Second Largest in Kotlin: Sort and Scan 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

    KOTLIN · SORTING

    Find Second Largest in Kotlin, explained

    Problem overview

    secondLargest takes an IntArray named nums and returns its second largest value. Duplicates of the maximum don't count as the second largest. The array is guaranteed to hold at least two distinct values.

    For [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, which appears three times, and the second largest value is 8.

    Approach

    There is a trap here: after sorting, the second element from the end is not necessarily the answer. The sorted example is [2, 3, 7, 8, 8, 11, 11, 11], and the second-to-last element is 11, the maximum again. The question asks for the largest value that differs from the maximum.

    So the plan is to sort ascending, which puts the maximum at the last index, and then walk backward from the end. The first element that is not equal to the maximum is the second largest value, because everything after it equals the maximum and everything before it is smaller or equal.

    This costs O(n log n) because of the sort. The statement's follow-up asks whether one pass without sorting is possible: it is, by tracking the two largest distinct values as you scan. This lesson uses the sort because it is easier to reason about.

    Step by step

    1. Sort nums in place with sort(), so the maximum sits at index nums.size - 1.
    2. Loop backwards with for (i in nums.size - 2 downTo 0). It starts at the second-to-last index, because the last element is the maximum itself, and goes down to index 0.
    3. Compare with the maximum. Inside the loop, check whether nums[i] differs from nums[nums.size - 1]. Elements equal to the maximum are duplicates and are skipped.
    4. Return the first different value, nums[i]. Scanning from the back, it is the largest value below the maximum.
    5. Add a fallback return -1 after the loop. The problem guarantees two distinct values, so it is never reached, but Kotlin requires every path through a function with a return type to return.

    The solution in Kotlin

    class Solution {
    fun secondLargest(nums: IntArray): Int {
        nums.sort()
        for (i in nums.size - 2 downTo 0) {
            if (nums[i] != nums[nums.size - 1]) {
                return nums[i]
            }
        }
        return -1
    }
}

    Kotlin details worth knowing:

    • a downTo b counts down and includes both ends. The expression nums.size - 2 downTo 0 is read as (nums.size - 2) downTo 0, because arithmetic binds tighter than the infix downTo.
    • If the array has only one element, nums.size - 2 is -1 and the range -1 downTo 0 is empty, so the loop doesn't run and the function returns -1. The same happens if all elements are equal.
    • A return inside a for loop leaves the whole function immediately.
    • The caller's array ends up sorted, because sort() works in place.

    Complexity

    • Time: O(n log n) for the sort. The backward scan is O(n) in the worst case, when the maximum fills most of the array.
    • Space: O(1) extra, since the sort is in place.

    Edge cases and common mistakes

    • Returning nums[nums.size - 2] directly. It fails whenever the maximum repeats, as in the example, where it returns 11 instead of 8.
    • Negative numbers. They work as they are: for [-3, -1] the answer is -3. This is why the fallback uses -1 only as an unreachable placeholder; a real answer could also be -1.
    • Two distinct values only. [5, 5, 9] returns 5, because the scan skips nothing but the maximum.
    • Starting the loop at the last index. The element would be compared with itself, never differ, and add nothing.
    • Using sorted() by mistake. nums.sorted() returns a new list and leaves nums unsorted, so the following indexing reads the wrong order.

    Testing

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