LESSON 357 OF 414 · GREEDY

Find Second Largest in Scala: One Pass Without Sorting

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

Guided

Ctrl + Enter to check

SCALA · GREEDY

Find Second Largest in Scala, explained

Problem overview

The method secondLargest receives nums, an Array[Int], and returns the second largest value. Duplicates of the maximum don't count as a second place. For [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, appearing three times, and the second largest value is 8. The array is guaranteed to contain at least two distinct values, and the follow-up asks for a single pass without sorting.

Approach: track the top two values

Sorting the array and reading the second element from the end is simple but costs O(n log n), and duplicates of the maximum would still need to be skipped. Instead, scan once while keeping two variables: maxVal, the largest value so far, and second, the largest value seen that is smaller than maxVal.

Each number falls into one of three cases:

It beats maxVal. The old maximum becomes the runner-up, and the number becomes the new maximum.
It is smaller than maxVal but bigger than second. It becomes the new runner-up.
Anything else, which includes a repeat of the maximum, changes nothing.

Both variables start at Int.MinValue, the smallest possible Int. Any real element beats that, so the first iteration needs no special treatment.

Trace [2, 7, 11, 8, 11]:

2: beats the minimum value, so second becomes Int.MinValue and maxVal becomes 2.
7: beats 2, so second = 2 and maxVal = 7.
11: beats 7, so second = 7 and maxVal = 11.
8: smaller than 11 and bigger than 7, so second = 8.
11: equal to maxVal, so nothing changes.

Continuing with the rest of the example, 8 is smaller than 11 and bigger than 7, so it only changes second; the next 11 and the next 8 change nothing, because neither is strictly between the two trackers; and 3 is below second. The final second is 8.

A simpler alternative

If one pass isn't required, you can drop the duplicates, sort, and take the second element from the end. For the example, nums.distinct.sorted is Array(2, 3, 7, 8, 11), and nums.distinct.sorted.reverse(1) gives 8. The code is shorter, but it allocates new arrays and takes O(n log n) time. The scan above answers the follow-up question with no sorting and no extra arrays.

Step by step

Declare maxVal and second as vars, both set to Int.MinValue.
Loop over nums with for (num <- nums), so each element can update the trackers.
Test for a new maximum with num > maxVal.
Demote, then replace. Inside that branch, copy maxVal into second first and only then assign num to maxVal. In the other order the old maximum would be lost.
Add an else if for values strictly below maxVal and strictly above second. The first bound keeps repeats of the maximum out. The second keeps a smaller value from replacing a better runner-up.
Assign num to second in that branch.
Return second after the loop.

The solution in Scala

class Solution {
    def secondLargest(nums: Array[Int]): Int = {
        var maxVal = Int.MinValue
        var second = Int.MinValue
        for (num <- nums) {
            if (num > maxVal) {
                second = maxVal
                maxVal = num
            } else if (num < maxVal && num > second) {
                second = num
            }
        }
        return second
    }
}

The Scala details worth a closer look:

Int.MinValue is -2147483648. Int in Scala has 32 bits, and arithmetic on it wraps silently on overflow. This solution only compares and copies values, so it never overflows.
var and for. The loop body assigns to vars declared outside it, which Scala allows. With val, the assignments would not compile.
&& and chained if/else if. Exactly one branch runs per element, and the else if condition is only evaluated when the first test fails.
Explicit return. The final return second works, although Scala code usually ends with second as the last expression.

Complexity

Time: O(n). One pass, with a constant number of comparisons per element.

Space: O(1). Two integers, regardless of the array size. Together with the single pass, this answers the follow-up: the work grows in step with the array, where sorting would grow faster, and nothing has to be copied.

Edge cases and common mistakes

Duplicates of the maximum. [5, 5, 3] returns 3. Without the num < maxVal test, the second 5 would be copied into second and the method would return 5.
Negative numbers. [-5, -3] returns -5. Starting both variables at 0 instead of Int.MinValue would give a wrong answer here.
Two elements. [1, 2] returns 1.
Descending input. [9, 1, 2] returns 2: the 1 becomes the runner-up first, then the 2 replaces it.
Overwriting in the wrong order. Assigning maxVal = num before second = maxVal makes both equal to num.
Fewer than two distinct values. [5, 5] returns -2147483648, because second never changes from its starting value. The array is guaranteed to have two distinct values, so this input doesn't occur in the lesson.
A real Int.MinValue. In an array such as [Int.MinValue, 5], the correct answer is also Int.MinValue, so the sentinel and the real value can't be told apart. That is harmless here, but it is the reason the "at least two distinct values" guarantee matters.

Testing

[2, 7, 11, 8, 11, 8, 3, 11] gives 8.
[5, 5, 3] gives 3.
[-5, -3] gives -5.
[1, 2] gives 1.
[9, 1, 2] gives 2.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free