Find the Second Maximum Value in an Array

Given an array of integers, return the second-largest distinct value. If the array has fewer than two distinct values, there's no answer.

Example 1

Text

Input:  [9, 2, 3, 6]
Output: 6

Example 2

Text

Input:  [4, 2, 1, 5, 5]
Output: 4
Explanation: 5 is the maximum. The second 5 is a duplicate, not a second maximum.

Example 3

Text

Input:  [7, 7]
Output: empty

Brute force: sort descending, remove duplicates, take index 1

OptionalInt is a container that holds either one int or nothing. OptionalInt.empty() reports "no answer" without returning null.

Java

import java.util.Arrays;
import java.util.OptionalInt;

public class Main {
    static OptionalInt secondMax(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted); // ascending
        int distinct = 0;    // number of distinct values seen from the largest end
        for (int i = sorted.length - 1; i >= 0; i--) {
            if (i == sorted.length - 1 || sorted[i] != sorted[i + 1]) {
                distinct++;
                if (distinct == 2) return OptionalInt.of(sorted[i]);
            }
        }
        return OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(secondMax(new int[]{9, 2, 3, 6}) + " " + secondMax(new int[]{4, 2, 1, 5, 5}) + " " + secondMax(new int[]{7, 7}));
    }
}

Output

OptionalInt[6] OptionalInt[4] OptionalInt.empty

Time: O(n log n). Space: O(n) for the copy. Sorting puts equal values next to each other, so the scan counts a new distinct value only when it differs from its larger neighbour. The code sorts a copy with clone() so the input stays unchanged.

Two passes: find the max, then the largest value below it

Java

import java.util.Arrays;
import java.util.OptionalInt;

public class Main {
    static OptionalInt secondMax(int[] nums) {
        if (nums.length == 0) return OptionalInt.empty();
        int max = Arrays.stream(nums).max().getAsInt();
        return Arrays.stream(nums).filter(x -> x < max).max();
    }

    public static void main(String[] args) {
        System.out.println(secondMax(new int[]{9, 2, 3, 6}) + " " + secondMax(new int[]{4, 2, 1, 5, 5}) + " " + secondMax(new int[]{7, 7}));
    }
}

Output

OptionalInt[6] OptionalInt[4] OptionalInt.empty

Time: O(n). Space: O(1). This is simple and already optimal in Big O terms. The one-pass version below does the same work while reading the input only once, which matters if the data comes from a stream.

Optimal: one pass, tracking the top two

Keep two slots, first (the largest so far) and second (the largest value strictly below first). For each x:

x > first: the old first becomes second, and x becomes first.
first > x > second: x becomes second.
x == first: ignore it, since duplicates of the maximum don't count.

Walkthrough with [4, 2, 1, 5, 5]:

x	case	first	second
4	new max	4	empty
2	between	4	2
1	smaller than both	4	2
5	new max	5	4
5	equal to max	5	4

Java

import java.util.OptionalInt;

public class Main {
    static OptionalInt secondMax(int[] nums) {
        boolean hasFirst = false, hasSecond = false;
        int first = 0, second = 0;
        for (int x : nums) {
            if (!hasFirst || x > first) {
                if (hasFirst) {
                    second = first;
                    hasSecond = true;
                }
                first = x;
                hasFirst = true;
            } else if (x != first && (!hasSecond || x > second)) {
                second = x;
                hasSecond = true;
            }
        }
        return hasSecond ? OptionalInt.of(second) : OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(secondMax(new int[]{9, 2, 3, 6}) + " " + secondMax(new int[]{4, 2, 1, 5, 5}) + " " + secondMax(new int[]{7, 7}));
        System.out.println(secondMax(new int[]{Integer.MIN_VALUE, 3}));
    }
}

Output

OptionalInt[6] OptionalInt[4] OptionalInt.empty
OptionalInt[-2147483648]

Time: O(n). Space: O(1).

The two boolean flags mean "nothing seen yet" for each slot. If the slots started at Integer.MIN_VALUE instead, [Integer.MIN_VALUE, 3] would be ambiguous: the result Integer.MIN_VALUE could be a real second maximum or a leftover initial value.

Edge cases

Empty array or one element: OptionalInt.empty().
All values equal: OptionalInt.empty().
Negative numbers: handled, since nothing assumes values are positive.
k-th largest in general: use a heap of size k, as in k largest elements.