Start learning free

LESSON 228 OF 414 · SORTING

Find Second Largest in Scala: O(n log n) with Sorting

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

    SCALA · SORTING

    Find Second Largest in Scala, explained

    Problem overview

    The method secondLargest receives an array of integers and returns its second largest value. Duplicates of the maximum don't count as the second place. For [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, which appears three times, and the second largest value is 8. You may assume the array has at least two distinct values.

    Approach: sort, then look from the back

    Once the array is sorted ascending, the maximum is the last element. The second largest value is the first element, scanning backwards, that is different from the maximum. Skipping equal values is what handles duplicates: in [2, 3, 7, 8, 8, 11, 11, 11] the scan passes over the three 11s and stops at 8.

    This costs O(n log n) for the sort and at most O(n) for the scan. The statement's follow-up asks whether one pass without sorting is possible. It is: keep the largest and the second largest seen so far and update both as you go. This lesson takes the simpler route, and its logic is easier to check.

    Step by step

    1. Make a sorted copy. val sorted = nums.sorted gives a new ascending array and leaves the input unchanged.
    2. Scan from the second-to-last index down to 0. The last index holds the maximum, so the scan starts one position before it and moves left.
    3. Compare with the maximum. If sorted(i) differs from sorted(sorted.length - 1), it isn't a copy of the maximum.
    4. Return it. Because the array is sorted, the first different value from the back is the second largest.
    5. Add a fallback. If the loop ends without returning, every element equals the maximum, and the method returns -1. With the guaranteed two distinct values that line never runs, but the method needs a value on every path.

    The solution in Scala

    class Solution {
    def secondLargest(nums: Array[Int]): Int = {
        val sorted = nums.sorted
        for (i <- sorted.length - 2 to 0 by -1) {
            if (sorted(i) != sorted(sorted.length - 1)) {
                return sorted(i)
            }
        }
        return -1
    }
}

    The Scala details worth knowing:

    • Counting down with by -1. a to b by -1 is a range that starts at a and steps down to b, with b included. Here it visits sorted.length - 2, then one less each time, down to 0. Because to includes its end, index 0 is checked. sorted.length - 2 until 0 by -1 would stop before 0.
    • Operator precedence in the range. Writing sorted.length - 2 to 0 by -1 parses as ((sorted.length - 2) to 0) by -1, because arithmetic binds tighter than the range methods.
    • return inside a for. A for loop over a range is translated to a call of foreach with a function, so return inside it leaves the whole method from inside that function. This works, but Scala 3.5 reports a warning that non-local returns are no longer supported and suggests scala.util.boundary. A while loop avoids the warning, because return there is an ordinary one.
    • The local name sorted is an ordinary val and has nothing to do with the sorted method called in nums.sorted.
    • Parentheses index arrays. sorted(i) reads an element.

    Complexity

    Time: O(n log n). Sorting dominates. The backward scan is O(n) in the worst case, when the maximum repeats many times.

    Space: O(n) for the sorted copy.

    Edge cases and common mistakes

    • Repeated maximum. [11, 11, 3] gives 3. Simply returning sorted(sorted.length - 2) would give 11 here, which is wrong.
    • Two elements. [1, 2] gives 1.
    • Negative numbers. [-5, -5, -9] gives -9.
    • All values equal. This breaks the guarantee. The code returns -1, which could also be a real answer, so input of this kind would need a different design.
    • Starting the scan at the last index. The element would be compared with itself and never differ, so it is just wasted work.
    • Stopping the range before 0. With until instead of to, the smallest element is never examined, and [1, 2] would return -1.

    Testing

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