Find the Second Maximum Without Counting Duplicates

The second maximum must be strictly smaller than the maximum

The second maximum is the largest distinct value that is smaller than the maximum element. In the array [5, 5, 7, 7, 2], the maximum is 7. The two copies of 7 represent one value, not two positions in a ranking, so the second maximum is 5.

The prefix [5, 5] shows why the answer may not exist. It has two positions, but both positions contain the same distinct value. There is no value strictly smaller than 5, so this prefix has no second maximum. The number of elements alone does not decide whether a second maximum exists.

Each scanned prefix can preserve its largest two distinct values

During the array traversal, keep the smallest complete summary of the values seen so far: largest, secondLargest, and hasSecond. largest stores the greatest distinct value in the scanned prefix. secondLargest stores the greatest distinct value below largest whenever one exists. hasSecond records whether secondLargest currently represents a real value.

After scanning each prefix of [5, 5, 7, 7, 2], these three variables are enough to answer the problem for that prefix. You do not need to store the prefix again or sort it. The state after [5, 5] is largest = 5 and hasSecond = false. After the first 7 is included, the state becomes largest = 7, secondLargest = 5, and hasSecond = true.

int largest = arr[0];
int secondLargest = 0;
bool hasSecond = false;

for (int i = 1; i < n; i++) {
    int x = arr[i];

    // Update largest, secondLargest, and hasSecond here.
}

A new maximum pushes the old maximum into second place

For each current value x, compare it with the two distinct candidates. If x is greater than largest, copy the old largest into secondLargest before replacing largest with x, and set hasSecond to true. If x is strictly between largest and secondLargest, replace secondLargest with x. If x equals either candidate, change nothing, because a duplicate does not create a new distinct value.

There is one extra case before a second candidate exists. If x is smaller than largest while hasSecond is false, x becomes secondLargest and hasSecond becomes true. This does not happen for the second 5 in the running array because it equals largest. When the first 7 arrives after [5, 5], the old largest 5 must be saved first, or the only possible second maximum will be lost.

if (x > largest) {
    secondLargest = largest;
    largest = x;
    hasSecond = true;
} else if (x < largest && (!hasSecond || x > secondLargest)) {
    secondLargest = x;
    hasSecond = true;
}
// If x equals largest or secondLargest, neither candidate changes.

The scanned prefix is [5, 5, 7].

The value -1 is an output rule, not a candidate value

Use hasSecond to decide what to print after the scan. If it is true, print secondLargest. If it is false, print -1 because no second maximum exists. For the full array [5, 5, 7, 7, 2], the final state has largest = 7, secondLargest = 5, and hasSecond = true, so the output is 5. For the prefix [5, 5], hasSecond remains false, so the output would be -1.

The scan examines each element once, so its time complexity is O(n). It keeps only largest, secondLargest, hasSecond, and a few loop variables, so its extra space complexity is O(1). Duplicate 7 values and the final 2 do not change the final state: the two distinct candidates remain 7 and 5.