LESSON 329 OF 344 · GREEDY

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

JAVA · GREEDY

Find Second Largest in Java, explained

Problem overview

The method secondLargest receives an int[] named nums and returns its second largest value. Duplicates don't count twice: in [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, which appears three times, and the second largest is 8, not 11. The array is guaranteed to hold at least two distinct values, so an answer always exists.

The follow-up asks for a single pass and no sorting, which is what this lesson does.

Approach: track two numbers while scanning

The easy route sorts the array and walks back from the end to the first value that differs from the maximum. That works, but it costs O(n log n) time and, in Java, reorders the caller's array. A single scan can do better, because the answer only depends on the two largest distinct values seen so far.

Keep two variables, max and second, and update them for each number:

If the number beats max, the old maximum becomes the runner-up and the number becomes the new maximum.
Otherwise, if the number is below max but above second, it is a better runner-up.
Otherwise it changes nothing. That includes numbers equal to max, which are exactly the duplicates that must not be counted as the second largest.

Trace [2, 7, 11, 8, 11, 8, 3, 11], with both variables starting at the smallest possible int:

num  max  second
 2     2    MIN
 7     7    2
11    11    7
 8    11    8
11    11    8   (equal to max, ignored)
 8    11    8   (equal to second, ignored)
 3    11    8
11    11    8

The scan ends with second = 8.

Two simpler alternatives

Sorting a copy and walking back past the copies of the maximum is the most direct idea. It is correct, but it does more work than the question needs:

static int viaSort(int[] nums) {
    int[] copy = nums.clone();
    Arrays.sort(copy);
    int i = copy.length - 1;
    while (copy[i] == copy[copy.length - 1]) {
        i--;
    }
    return copy[i];
}

On the example array this returns 8. It needs the clone to keep the caller's array intact, and the loop relies on the guarantee of two distinct values to stop before i goes below zero.

A two-pass version finds the maximum first, then takes the largest element that isn't equal to it. This also returns 8 on the example, and it is O(n) too, but it reads the array twice. The one-pass scan above gets the same answer in a single loop, which is what the follow-up asks for.

Step by step

Declare max and second as ints set to Integer.MIN_VALUE, the smallest value an int can hold. Any real element is at least that large, so no special "first element" check is needed.
Loop over the array with a for-each loop and an int variable num.
Test for a new maximum with num > max.
Demote the old maximum, then replace it. Copy max into second first, and only then overwrite max with num. Reversed, the old maximum would be lost.
Test for a new runner-up in an else if: num < max and num > second. The first half excludes copies of the maximum, and the second half skips numbers that wouldn't improve on the current runner-up.
Assign it to second.
Return second after the loop.

The solution in Java

class Solution {
    public int secondLargest(int[] nums) {
        int max = Integer.MIN_VALUE;
        int second = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num > max) {
                second = max;
                max = num;
            } else if (num < max && num > second) {
                second = num;
            }
        }
        return second;
    }
}

Java details worth a closer look:

Integer.MIN_VALUE is -2147483648. It works as a "nothing yet" marker because no element can be smaller. Unlike 0, it also works when every element is negative.
The else if matters. A number that beats max must not also reach the second test, and because the first branch already ran, it never does.
Primitive arrays and the for-each loop. for (int num : nums) copies each element into num, so changing num wouldn't touch the array. This code only reads, and leaves the caller's array unsorted and unchanged.
No overflow. The code only compares and copies values and never adds them, so no int arithmetic can wrap around.

Complexity

Time: O(n). The loop looks at each element once and does a constant amount of work for each. Sorting would cost O(n log n).

Space: O(1). Two integers, whatever the array length.

Edge cases and common mistakes

Duplicates of the maximum. For [5, 5, 1] the answer is 1. Without the num < max test, the second 5 would be copied into second and the method would return 5.
Two elements. [1, 2] returns 1. The 1 becomes max first, then the 2 pushes it into second.
Ascending or descending order. Both are handled. In a descending array like [9, 8, 7], the later values reach the else if branch. In an ascending one, each new value demotes the previous maximum.
Negative numbers. [-4, -9, -4] returns -9. Starting the variables at 0 instead of Integer.MIN_VALUE would break this case.
Overwriting in the wrong order. Setting max = num before second = max makes both variables equal to the new value.
All values equal. [3, 3] has no second largest value. The input rules rule this out, but the code would return Integer.MIN_VALUE, since second never changes.

Testing

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

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

Start learning free