Second Largest Element

Sort the array in ascending order, then walk backwards past every copy of the largest value until you hit the first strictly smaller entry — that is the second largest distinct value.

If no such value exists (all elements equal), return -1.

// Sort ascending, then scan backwards past all copies of the largest
// to find the first strictly smaller value — the second distinct maximum.
// Time: O(n log n)  Space: O(n)
fn second_largest_naive(numbers: &[i64]) -> i64 {
    if numbers.len() < 2 {
        return -1;
    }
    let mut sorted: Vec<i64> = numbers.to_vec();
    sorted.sort();
    let largest: i64 = *sorted.last().unwrap();
    for &val in sorted.iter().rev().skip(1) {
        if val != largest {
            return val;
        }
    }
    -1
}

Time — O(n log n)

Sorting dominates; the reverse scan is O(n).

Space — O(n)

The sorted copy stores n elements.

Time: sorting the full array is overkill when only the top two distinct values matter.

Space: the sorted vector duplicates the input in memory.

Next step: find the largest in one scan, then the best non-largest in a second scan.

Pass 1: scan once to find largest = numbers.iter().max().

Pass 2: scan again. Ignore any value equal to largest. Track the maximum of the remaining values as second_largest.

If no value survives pass 2 (all elements equal to largest), return -1.

// Two-pass: find max first, then scan for the largest value strictly below it
fn second_largest_two_pass(numbers: &[i64]) -> i64 {
    if numbers.len() < 2 {
        return -1;
    }
    let largest = *numbers.iter().max().unwrap();
    let mut second_largest = i64::MIN;
    for &number in numbers {
        if number != largest && number > second_largest {
            second_largest = number;
        }
    }
    if second_largest == i64::MIN {
        -1
    } else {
        second_largest
    }
}

Time — O(n)

Pass 1: O(n) for max(). Pass 2: another O(n) scan → O(n) total.

Space — O(1)

Only largest and second_largest scalars — no extra collection.

Tradeoff: linear time, but the array is walked twice. Can we track both extrema in a single pass?

Maintain two variables in one left-to-right scan:

• first_largest — best value seen so far
• second_largest — best value strictly below first_largest

For each number:

1. If number > first_largest: demote old first to second, promote number to first.
2. Else if first_largest > number && number > second_largest: update second only.

After the scan, return second_largest if it was updated from i64::MIN; otherwise -1.

// Optimal: single pass tracking first and second distinct maximums
fn second_largest_optimal(numbers: &[i64]) -> i64 {
    if numbers.len() < 2 {
        return -1;
    }
    let mut first_largest = i64::MIN;
    let mut second_largest = i64::MIN;
    for &number in numbers {
        if number > first_largest {
            second_largest = first_largest;
            first_largest = number;
        } else if first_largest > number && number > second_largest {
            second_largest = number;
        }
    }
    if second_largest == i64::MIN {
        -1
    } else {
        second_largest
    }
}

Time — O(n)

Single pass: each element handled once with O(1) comparisons → O(n).

Space — O(1)

Two scalar variables only — no sorted buffer.

Result: same correctness as naive and two-pass, with O(n) time, O(1) space, and one scan instead of two.

Full source: Rust · Python