Majority Element

Return the element that appears more than ⌊n / 2⌋ times in an array.

TimeO(n)

SpaceO(1)

Given an array nums of size n, return the majority element — the value that appears more than ⌊n / 2⌋ times.

You may assume the majority element always exists in the array.

Constraints

Input: one line of space-separated integers.
Output: print the majority element on one line (once per approach in the reference solution).
Guarantee: exactly one value appears more than n // 2 times.

Input

3 2 3

Output

Explanation: 3 appears twice in three elements — more than ⌊3/2⌋ = 1.

Naive Solution

Sort the array in ascending order and return the element at index n // 2.

If a value appears more than half the time, it must occupy the middle position after sorting.

// After sorting, the majority element occupies the middle index.
// Time: O(n log n)  Space: O(1)
fn majority_element_sort(numbers: &mut [i64]) -> i64 {
    numbers.sort();
    numbers[numbers.len() / 2]
}

Time — O(n log n)

Sorting dominates.

Space — O(1)

In-place sort uses only constant extra space (ignoring sort stack).

Time: sorting the entire array is unnecessary when only one frequency count matters.

Next step: count frequencies with a hash map in a single pass.

Two-Pass Solution

Walk the array once with a frequency map. For each num, increment its count. Return num as soon as count[num] > n // 2.

Early exit — stop the moment a majority is confirmed.

// Tally counts; return as soon as any value exceeds n // 2.
// Time: O(n)  Space: O(n)
fn majority_element_hash_table(numbers: &[i64]) -> Option<i64> {
    let mut count: HashMap<i64, i32> = HashMap::new();
    let half = (numbers.len() / 2) as i32;
    for &num in numbers {
        let entry = count.entry(num).or_insert(0);
        *entry += 1;
        if *entry > half {
            return Some(num);
        }
    }
    None
}

Time — O(n)

Single pass with O(1) map updates per element.

Space — O(n)

The map stores one entry per distinct value.

Tradeoff: linear time, but O(n) extra space. Can we find the majority in O(1) space?

Optimal Solution

Boyer-Moore voting: maintain a candidate and a balance counter.

For each num:

If balance == 0, set candidate = num.
If num == candidate, increment balance; otherwise decrement it.

Mismatched pairs cancel out; the majority survives. When a majority is guaranteed, the final candidate is the answer.

// Maintain a candidate and a balance; mismatches cancel out.
// Time: O(n)  Space: O(1)
fn majority_element_boyer_moore(numbers: &[i64]) -> Option<i64> {
    let mut balance: i32 = 0;
    let mut candidate: Option<i64> = None;
    for &num in numbers {
        if balance == 0 {
            candidate = Some(num);
        }
        if Some(num) == candidate {
            balance += 1;
        } else {
            balance -= 1;
        }
    }
    candidate
}

Time — O(n)

One pass, O(1) work per element.

Space — O(1)

Only candidate and balance — no hash map.

Result: same answer as sort and hash map when a majority is guaranteed, with O(n) time and O(1) space.

Full source: Rust · Python