Majority element ii

Array Hash Table Sorting Counting

55.8% acceptance

Jan 12, 2026

10934

496

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn majority_element(nums: Vec<i32>) -> Vec<i32> {
    let mut candidate1 = 0;
    let mut candidate2 = 0;
    let mut count1 = 0;
    let mut count2 = 0;
    
    for &num in &nums {
      if num == candidate1 {
        count1 += 1;
      } else if num == candidate2 {
        count2 += 1;
      } else if count1 == 0 {
        candidate1 = num;
        count1 = 1;
      } else if count2 == 0 {
        candidate2 = num;
        count2 = 1;
      } else {
        count1 -= 1;
        count2 -= 1;
      }
    }
    
    count1 = 0;
    count2 = 0;
    for &num in &nums {
      if num == candidate1 {
        count1 += 1;
      } else if num == candidate2 {
        count2 += 1;
      }
    }
    
    let mut result = Vec::new();
    if count1 > nums.len() / 3 {
      result.push(candidate1);
    }
    if count2 > nums.len() / 3 {
      result.push(candidate2);
    }
    result
  }
}