Second Maximum Search

Second maximum search finds the element that is strictly smaller than the maximum and as large as possible. It mirrors second minimum search and tracks two candidates during a single scan.

This is a basic selection primitive used in ranking and tournament style algorithms.

Problem

Given a sequence $A$ of length $n$, find an index $i$ such that

$$ A[i] = \max {, A[j] \mid A[j] < \max(A) ,} $$

If no such element exists, return $-1$.

Idea

Maintain two values:

• largest element seen so far
• second largest element seen so far

Update both as the scan proceeds.

Algorithm

second_maximum_search(A):
    if length(A) < 2:
        return -1

    max_index = 0
    second_index = -1

    for i from 1 to length(A) - 1:
        if A[i] > A[max_index]:
            second_index = max_index
            max_index = i
        else if A[i] < A[max_index]:
            if second_index == -1 or A[i] > A[second_index]:
                second_index = i

    return second_index

Example

Let

$$ A = [7, 3, 5, 2, 9] $$

The scan proceeds:

step	index	value	max	second max
1	0	7	7	—
2	1	3	7	3
3	2	5	7	5
4	3	2	7	5
5	4	9	9	7

Return index of value $7$.

Correctness

At each step:

• max_index stores the largest element seen
• second_index stores the largest element smaller than the maximum

When a new maximum appears, the previous maximum becomes a candidate for second maximum. When a value lies between them, it updates the second maximum.

After processing all elements, both invariants ensure correctness.

Complexity

case	comparisons	time
all cases	$n - 1$	$O(n)$

Space usage:

$$ O(1) $$

When to Use

Use second maximum search when:

• selecting top two largest elements
• ranking or filtering tasks
• building tournament based selection

For general k-th largest selection, use algorithms like quickselect.

Implementation

def second_maximum_search(a):
    if len(a) < 2:
        return -1

    max_i = 0
    second_i = -1

    for i in range(1, len(a)):
        if a[i] > a[max_i]:
            second_i = max_i
            max_i = i
        elif a[i] < a[max_i]:
            if second_i == -1 or a[i] > a[second_i]:
                second_i = i

    return second_i

func SecondMaximumSearch[T constraints.Ordered](a []T) int {
    if len(a) < 2 {
        return -1
    }

    maxI := 0
    secondI := -1

    for i := 1; i < len(a); i++ {
        if a[i] > a[maxI] {
            secondI = maxI
            maxI = i
        } else if a[i] < a[maxI] {
            if secondI == -1 || a[i] > a[secondI] {
                secondI = i
            }
        }
    }

    return secondI
}