LESSON 333 OF 348 · GREEDY

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

KOTLIN · GREEDY

Find Second Largest in Kotlin, explained

Problem overview

The function secondLargest receives an IntArray named nums and returns its 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, and the second largest value is 8. The array always holds at least two distinct values.

The follow-up asks for one pass and no sorting, and that is what this lesson builds.

Approach: keep two trackers

The easy way is to sort the array, then walk back from the end until the value changes. It works, but it costs O(n log n) to order data when you only want the top two values. A single scan can do the job with two variables: maxVal, the largest value seen so far, and second, the largest value seen so far that is strictly smaller than maxVal.

Each element num falls into one of three cases:

num > maxVal: a new maximum. The old maximum becomes the runner-up and num takes first place.
num < maxVal and num > second: a better runner-up. Replace second.
Anything else: num equals the maximum, or it is no better than the current runner-up. Ignore it.

Trace the example. Both trackers start at Int.MIN_VALUE. Reading 2 gives maxVal = 2. Reading 7 gives maxVal = 7 and second = 2. Reading 11 gives maxVal = 11 and second = 7. Reading 8 is below 11 and above 7, so second = 8. The next 11 equals the maximum and is ignored, so duplicates of the maximum can't take second place. The next 8 and then 3 change nothing, and the final 11 is ignored. The function returns 8.

The sorting route is short in Kotlin. nums.distinct().sortedDescending()[1] removes repeated values, orders what is left from largest to smallest and takes the element at index 1; for the example it gives 8. Both calls build new collections, so that costs O(n log n) time and O(n) extra space. The two-tracker scan gives the same answer with neither cost, and it also shows a pattern that returns later in greedy problems: keep only the few values that can still change the answer, and update them as each element arrives.

The invariant that makes the scan correct is simple. After every element, maxVal is the largest value read so far and second is the largest value read so far that is strictly smaller than maxVal. Each of the three cases keeps both statements true, so when the loop ends they describe the whole array.

Step by step

Declare maxVal and second as var, both set to Int.MIN_VALUE. Any real element is at least that large, so the first element needs no special treatment.
Loop over nums with num as the loop variable, so that every element can update the trackers.
Test for a new maximum with num > maxVal.
Demote before you overwrite. Inside that branch, copy maxVal into second first and then assign num to maxVal. In the opposite order, the old maximum is lost.
Add an else if for values strictly below maxVal and strictly above second. The first strictness keeps ties with the maximum out, and the second avoids useless writes.
Update second to num in that branch.
Return second after the loop.

The solution in Kotlin

class Solution {
    fun secondLargest(nums: IntArray): Int {
        var maxVal = Int.MIN_VALUE
        var second = Int.MIN_VALUE
        for (num in nums) {
            if (num > maxVal) {
                second = maxVal
                maxVal = num
            } else if (num < maxVal && num > second) {
                second = num
            }
        }
        return second
    }
}

The Kotlin details worth a closer look:

Int.MIN_VALUE is the smallest Int, -2147483648. It acts as a "nothing yet" marker, which works because no Int in the array can be smaller.
for (num in nums) iterates over the elements directly, with no index. The loop variable is read-only, which is fine because the code only reads it.
var is needed. Both trackers are reassigned, so val would not compile.
if / else if is used as a statement. At most one branch runs per element, and the else in else if is what keeps a new maximum from also going through the second test.
The array is left alone. The function only reads nums. Calling nums.sort() instead would reorder the caller's array in place, which is a side effect the scan avoids.

Complexity

Time: O(n). One loop visits each element once and does a constant number of comparisons.

Space: O(1). Two integers and the loop variable, regardless of the array size.

Edge cases and common mistakes

Duplicates of the maximum. [5, 5, 1] returns 1, not 5. The strict num < maxVal test is what makes duplicates of the maximum harmless. With <=, the second 5 would become the runner-up.
Negative numbers. [-5, -2, -9] returns -5. Starting the trackers at 0 would be a bug here, because no negative value would ever beat 0; Int.MIN_VALUE avoids this.
Increasing order. In [1, 2, 3, 4], every element is a new maximum, and the demotion step carries the previous maximum into second. The result is 3.
Decreasing order. In [9, 7, 5], 9 is the maximum and 7 takes second place through the else if branch. The result is 7.
Wrong order inside the first branch. Assigning maxVal = num before second = maxVal sets both to num.
No second distinct value. The lesson promises two distinct values, but for [3, 3, 3] the function returns Int.MIN_VALUE, since second never changes. Callers who can't promise that should check for it.

Testing

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

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

Start learning free