Third Largest Element

Find the third largest element in an array of n integers, or return -1 when fewer than three elements exist.

TimeO(n)

SpaceO(1)

Given an array of n integers, find the third largest element.

Constraints

Input: one line of space-separated integers (read from stdin with split_whitespace()).
Output: print a single integer on one line.
Answer rule: return the third largest element when the array is sorted in descending order (duplicates count as separate positions).
No valid answer: if the array has fewer than three elements, print -1.
Duplicates: repeated values still occupy rank — in [5, 5, 5], the third largest is 5.

Input

2 4 1 3 5

Output

Explanation: Sorted ascending: 1, 2, 3, 4, 5. The element at index len−3 is 3.

Naive Solution

Sort the array in ascending order and return the element at index len − 3.

If len(arr) < 3, return -1.

Duplicates are kept during sorting, so equal values fill consecutive rank slots.

// Sort ascending; the third-largest is at index len-3.
// Duplicates are kept, so equal values fill consecutive rank slots.
// Time: O(n log n)  Space: O(n)
fn third_largest_naive(numbers: &[i64]) -> i64 {
    if numbers.len() < 3 {
        return -1;
    }
    let mut sorted: Vec<i64> = numbers.to_vec();
    sorted.sort();
    sorted[sorted.len() - 3]
}

Space — O(n)

sorted() builds a new list of length n.

Time: sorting every element is unnecessary when only the third maximum is needed.

Space: a sorted copy duplicates the array.

Next step: three independent max-finding passes avoid sorting while still using only O(1) extra space. A single-pass cascade eliminates the repeated scans entirely.

Three-Pass Solution

Make three left-to-right scans. Each pass finds the maximum while skipping the index (not the value) of the previously found rank:

Pass 1 — find the overall maximum and record its index.
Pass 2 — find the maximum among all indices except first_idx.
Pass 3 — find the maximum among all indices except first_idx and second_idx.

Skipping by index means duplicate values at different positions are valid candidates for successive ranks — required for [5, 5, 5] and [100, 100, 100, 99, 98].

Guard first: if len(numbers) < 3, return -1.

// Three independent scans, each finding the next rank by skipping the
// *index* (not the value) of the previously found rank.
// Skipping by index means duplicate values at different positions are
// valid candidates for successive ranks.
// Time: O(n)  Space: O(1)
fn third_largest_three_pass(numbers: &[i64]) -> i64 {
    if numbers.len() < 3 {
        return -1;
    }
 
    let mut first = i64::MIN;
    let mut second = i64::MIN;
    let mut third = i64::MIN;
    let mut first_idx: Option<usize> = None;
    let mut second_idx: Option<usize> = None;
    let mut third_idx: Option<usize> = None;
 
    // Pass 1: find the overall maximum and its first-occurrence index.
    for (idx, &number) in numbers.iter().enumerate() {
        if number > first {
            first = number;
            first_idx = Some(idx);
        }
    }
 
    // Pass 2: find the maximum while skipping first_idx.
    for (idx, &number) in numbers.iter().enumerate() {
        if Some(idx) == first_idx {
            continue;
        }
        if number > second {
            second = number;
            second_idx = Some(idx);
        }
    }
 
    // Pass 3: find the maximum while skipping both first_idx and second_idx.
    for (idx, &number) in numbers.iter().enumerate() {
        if Some(idx) == first_idx || Some(idx) == second_idx {
            continue;
        }
        if number > third {
            third = number;
            third_idx = Some(idx);
        }
    }
 
    if third_idx.is_some() { third } else { -1 }
}

Time — O(n)

Three linear scans: 3n comparisons → O(n).

Space — O(1)

Six scalar variables (three values + three indices).

Optimal Solution

Maintain first, second, and third in a single left-to-right scan using strict > comparisons:

if number > first:      third, second, first = second, first, number
elif number > second:   third, second = second, number
elif number > third:    third = number

Guard first: if len(numbers) < 3, return -1.

Duplicate values naturally cascade into lower rank slots via the elif chain because float("-inf") is always beaten first — a second 10 updates second even though it does not beat first. This handles [5, 5, 5] and [100, 100, 100, 99, 98] correctly.

// Single pass: maintain three rank variables with strict > comparisons.
// Duplicate values naturally cascade into lower rank slots via the
// else-if chain because i64::MIN is always beaten first.
// Time: O(n)  Space: O(1)
fn third_largest_optimal(numbers: &[i64]) -> i64 {
    if numbers.len() < 3 {
        return -1;
    }
 
    let mut first = i64::MIN;
    let mut second = i64::MIN;
    let mut third = i64::MIN;
 
    for &number in numbers {
        if number > first {
            // New overall maximum: demote first → second, second → third.
            third = second;
            second = first;
            first = number;
        } else if number > second {
            // Beats second but not first: demote second → third only.
            third = second;
            second = number;
        } else if number > third {
            // Beats only the current third.
            third = number;
        }
    }
 
    if third == i64::MIN { -1 } else { third }
}

Time — O(n)

Single pass, O(1) work per element.

Space — O(1)

Three scalar variables only.

Full source: Rust · Python

Time — O(n log n)

Space — O(n)

Time — O(n)

Space — O(1)

Time — O(n)

Space — O(1)