Topics › Arrays › Easy

Second Largest Element

Easy TUF ID 43 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array of integers nums. Return the second largest distinct value, that is, the largest value that is strictly smaller than the maximum. If no such value exists (the array has fewer than two elements, or every element is equal), return -1. The sheet pairs this with the mirror question, the second smallest distinct value, and the same idea answers both.

Constraints: 0 ≤ n ≤ 10^5, values fit in a 32-bit signed integer and may be negative. The classic version promises that the input values are non-negative so that -1 is unambiguous as a “not found” marker; see the pitfalls for what happens without that promise.

Example 1

nums = [1, 2, 4, 7, 7, 5]
second largest = 5      // the maximum 7 appears twice, but 7 is not "second largest"; 5 is
second smallest = 2

Example 2

nums = [7, 7, 7]
second largest = -1     // only one distinct value exists

Example 3

nums = [5, 5, 4]
second largest = 4      // duplicates of the maximum do not count

The word distinct is the whole problem. “Second largest” is not “the element at index n - 2 after sorting”; with [7, 7, 5] that would wrongly give 7.

Approach 1: Brute force, sort and walk down

Intuition. After sorting, the maximum is at the end. The second largest distinct value is the first element, scanning from the right, that differs from the maximum. Because the array is sorted, “differs from” means “is smaller than”, and the first such element is the largest of the smaller ones.

Algorithm.

1. If n < 2, return -1.
2. Sort a copy of nums.
3. Let largest = a[n - 1]. For i from n - 2 down to 0: if a[i] != largest, return a[i].
4. If the loop finishes, every element equals the maximum; return -1.

static int bruteForce(int[] nums) {
    int n = nums.length;
    if (n < 2) return -1;
    int[] a = nums.clone();
    Arrays.sort(a);
    int largest = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        if (a[i] != largest) return a[i];        // first value strictly below the maximum
    }
    return -1;                                   // every element equals the maximum
}

Complexity. Time O(n log n) for the sort; the backward walk is O(n) in the worst case (all duplicates). Space O(n) for the copy.

Sorting is overkill for the same reason as in Largest Element: we only need two pieces of information, not the complete order.

Approach 2: Better, two linear passes

Intuition. First find the maximum with a plain scan. Then scan again, this time ignoring every element equal to the maximum, and take the biggest of what remains. The second pass is itself a “largest element” scan over a filtered view of the array.

The subtle part is initialising the second pass. Using Integer.MIN_VALUE as “nothing found yet” fails if Integer.MIN_VALUE really is the second largest value, so a separate found flag records whether any candidate has been seen.

Algorithm.

1. If n < 2, return -1.
2. Pass 1: largest = max(nums).
3. Pass 2: for every x != largest, if nothing has been found yet or x > second, set second = x and mark found.
4. Return second if found, else -1.

static int better(int[] nums) {
    if (nums.length < 2) return -1;
    int largest = nums[0];
    for (int x : nums) if (x > largest) largest = x;
    boolean found = false;
    int second = Integer.MIN_VALUE;
    for (int x : nums) {
        if (x != largest && (!found || x > second)) {
            second = x;
            found = true;
        }
    }
    return found ? second : -1;
}

Complexity. Time O(n): two passes, each O(n). Space O(1).

This is already optimal in big-O terms. The one-pass version below does the same work with half the memory traffic, and more importantly it is the pattern that generalises to streaming input where you cannot go back for a second look.

Approach 3: Optimal, one pass carrying two values

Intuition. Carry largest and second together. When a new element x arrives, there are exactly three interesting cases:

• x > largest: x is the new champion, and the old champion becomes the runner-up.
• largest > x > second: x slots in as the new runner-up.
• otherwise (x == largest, or x <= second): nothing changes.

The equality case x == largest is what enforces distinctness: a duplicate of the maximum must not be demoted into second. That is why the second condition is x < largest, not x <= largest.

Sentinels: both variables start at Long.MIN_VALUE, declared as long. No int can equal that value, so second == Long.MIN_VALUE at the end means unambiguously “no second distinct value was ever seen”, even if the array contains Integer.MIN_VALUE.

Algorithm.

1. If n < 2, return -1.
2. largest = second = Long.MIN_VALUE.
3. For each x: apply the three-case update above.
4. Return -1 if second is still the sentinel, else (int) second.

static int optimal(int[] nums) {
    if (nums.length < 2) return -1;
    long largest = Long.MIN_VALUE, second = Long.MIN_VALUE;   // long: no int value can collide with the sentinel
    for (int x : nums) {
        if (x > largest) {
            second = largest;                    // the old maximum is now the runner-up
            largest = x;
        } else if (x < largest && x > second) {
            second = x;                          // between the two: new runner-up
        }
    }
    return second == Long.MIN_VALUE ? -1 : (int) second;
}

Dry run on nums = [1, 2, 4, 7, 7, 5] (-∞ stands for Long.MIN_VALUE):

Answer 5.

Complexity. Time O(n), a constant number of comparisons per element. Space O(1).

The mirror image: second smallest

Flip every comparison and swap the sentinels for Long.MAX_VALUE:

static int secondSmallest(int[] nums) {
    if (nums.length < 2) return -1;
    long smallest = Long.MAX_VALUE, second = Long.MAX_VALUE;
    for (int x : nums) {
        if (x < smallest) {
            second = smallest;
            smallest = x;
        } else if (x > smallest && x < second) {
            second = x;
        }
    }
    return second == Long.MAX_VALUE ? -1 : (int) second;
}

Same complexity, same three cases. Once you see the symmetry, you can write either direction from memory.

Edge cases and pitfalls

• Fewer than two elements. [] and [1] return -1 immediately. Every method checks this before touching nums[0].
• All elements equal. [7, 7, 7] has one distinct value, so the answer is -1. The one-pass method never enters the else if branch because x < largest is false for every duplicate.
• Duplicated maximum with a smaller value present. [5, 5, 4] must return 4, not 5. Taking “the element before the last after sorting” gets this wrong.
• Integer.MIN_VALUE as a real value. [Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MAX_VALUE] has second largest Integer.MIN_VALUE. An int sentinel equal to that value would report -1. Use long sentinels or an explicit found flag; the file does both, in different methods, and the tests cover this input.
• -1 is ambiguous when negatives are allowed. [-1, 5] has second largest -1, which is indistinguishable from “not found”. The classic statement restricts values to be non-negative for exactly this reason. If your inputs may be negative, return an OptionalInt or throw instead; the logic does not change.
• Strict versus non-strict comparisons. x < largest && x > second must be strict on both sides: <= on the left would let a duplicate of the maximum become the runner-up, and >= on the right only wastes a write.
• Do not reorder the input. bruteForce sorts a clone; the tests assert the original array is untouched.

Related problems

• Largest Element is the one-variable version of the same scan.
• Linear Search is the other fundamental single-pass array walk.
• Remove duplicates from Sorted array is about the same notion of “distinct values” in a sorted setting.
• K-th largest element in an array asks for the general k; a two-variable scan no longer suffices and a heap or quickselect takes over.