Majority element

Array Hash Table Divide and Conquer Sorting Counting

66.1% acceptance

Jan 12, 2026

22586

806

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn majority_element(nums: Vec<i32>) -> i32 {
    let mut candidate = 0;
    let mut count = 0;
    
    for &num in &nums {
      if count == 0 {
        candidate = num;
        count = 1;
      } else if num == candidate {
        count += 1;
      } else {
        count -= 1;
      }
    }
    
    candidate
  }
}