Find Majority Element in Array (more than n/3 times)

Given an integer array arr, your task is to find all elements that appear more than ⌊n/3⌋ times in the array, where n is the size of the array.

• You may return the results in any order.
• There can be at most 2 such elements in any array.

If no such element exists, return an empty list.

Understanding the Problem

We are given an array of integers, and our goal is to find all elements that appear more than ⌊n/3⌋ times. In other words, we want to identify elements that show up frequently—but not necessarily the most frequent one.

This isn’t about just counting and checking frequencies using a hashmap—we want to solve this problem efficiently: in linear time and using constant space.

Step-by-Step Plan with Example

Let’s take the example: [3, 2, 3]

Step 1: What does ⌊n/3⌋ mean?

The length of the array n = 3. So ⌊n/3⌋ = ⌊1⌋ = 1. That means we want all elements that occur more than once in this array.

Step 2: Why are there at most two valid elements?

Let’s imagine we have three different numbers, and each of them appears more than ⌊n/3⌋ times. That would be more than n total elements, which is impossible. Hence, we can have at most two elements that satisfy this condition.

Step 3: Using Extended Boyer-Moore Voting Algorithm

This is a clever trick to keep track of up to two candidates:

• We maintain two variables for candidates and their counts.
• If we see the same number again, we increment its count.
• If a count drops to zero, we replace that candidate with the new number.
• If the number doesn’t match either candidate, we decrement both counts.

This way, after the first pass, we end up with at most two candidates who could be the majority elements. But we still need to verify them.

Step 4: Final Verification

Once we have our two candidates, we do a second pass through the array to count their actual occurrences. If either one appears more than ⌊n/3⌋ times, we include it in the final result.

Let’s Solve the Example

Input: [3, 2, 3]

First Pass:
- candidate1 = 3, count1 = 1
- candidate2 = 2, count2 = 1
- next 3: matches candidate1 → count1 becomes 2

Second Pass:
- count of 3 = 2
- count of 2 = 1

Since ⌊3/3⌋ = 1:
→ 3 appears more than once ⇒ include it
→ 2 appears only once ⇒ do not include it

Output: [3]

Edge Cases and How We Handle Them

1. Empty Array

If the array is empty, there are no elements to check. So, we return an empty list.

2. Single Element

If the array has just one element, that element is trivially more than ⌊n/3⌋ times. So we return it.

3. All Unique Elements

Example: [1, 2, 3]. Here, each element appears once, and ⌊3/3⌋ = 1. So none appear more than that ⇒ return empty list.

4. Two Valid Candidates

Example: [1, 1, 1, 2, 2, 2, 3]
n = 7 → ⌊n/3⌋ = 2
1 appears 3 times → valid
2 appears 3 times → valid
Output: [1, 2]

1. Given an array arr of size n.
2. Initialize two candidates candidate1 and candidate2 and their counts to 0.
3. Traverse the array:
4. → If the current element equals candidate1, increment count1.
5. → Else if it equals candidate2, increment count2.
6. → Else if count1 is 0, set candidate1 to current element and count1 to 1.
7. → Else if count2 is 0, set candidate2 to current element and count2 to 1.
8. → Else decrement both count1 and count2.
9. After the first pass, verify the candidates by counting their actual occurrences in the array.
10. Return the candidates that appear more than n/3 times.

#include <stdio.h>

void majorityElements(int arr[], int n) {
    int candidate1 = 0, candidate2 = 1, count1 = 0, count2 = 0;

    for (int i = 0; i < n; i++) {
        if (arr[i] == candidate1) count1++;
        else if (arr[i] == candidate2) count2++;
        else if (count1 == 0) { candidate1 = arr[i]; count1 = 1; }
        else if (count2 == 0) { candidate2 = arr[i]; count2 = 1; }
        else { count1--; count2--; }
    }

    count1 = count2 = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == candidate1) count1++;
        else if (arr[i] == candidate2) count2++;
    }

    printf("Majority Elements: ");
    if (count1 > n/3) printf("%d ", candidate1);
    if (count2 > n/3 && candidate1 != candidate2) printf("%d ", candidate2);
    printf("\n");
}

int main() {
    int arr[] = {3, 2, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    majorityElements(arr, n);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

vector<int> majorityElements(vector<int>& arr) {
    vector<int> result;
    int n = arr.size();
    if (n == 0) return result;

    int candidate1 = 0, candidate2 = 1, count1 = 0, count2 = 0;

    for (int num : arr) {
        if (num == candidate1) count1++;
        else if (num == candidate2) count2++;
        else if (count1 == 0) { candidate1 = num; count1 = 1; }
        else if (count2 == 0) { candidate2 = num; count2 = 1; }
        else { count1--; count2--; }
    }

    count1 = count2 = 0;
    for (int num : arr) {
        if (num == candidate1) count1++;
        else if (num == candidate2) count2++;
    }

    if (count1 > n/3) result.push_back(candidate1);
    if (count2 > n/3 && candidate1 != candidate2) result.push_back(candidate2);

    return result;
}

int main() {
    vector<int> arr = {3, 2, 3};
    vector<int> result = majorityElements(arr);
    cout << "Majority Elements: ";
    for (int num : result) cout << num << " ";
    cout << endl;
    return 0;
}

def majority_elements(arr):
    if not arr:
        return []

    candidate1 = candidate2 = None
    count1 = count2 = 0

    for num in arr:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1
        elif count1 == 0:
            candidate1 = num
            count1 = 1
        elif count2 == 0:
            candidate2 = num
            count2 = 1
        else:
            count1 -= 1
            count2 -= 1

    result = []
    for candidate in [candidate1, candidate2]:
        if arr.count(candidate) > len(arr) // 3:
            result.append(candidate)
    return result

arr = [3, 2, 3]
print("Majority Elements:", majority_elements(arr))

import java.util.*;

public class MajorityElements {
    public static List<Integer> findMajorityElements(int[] arr) {
        List<Integer> result = new ArrayList<>();
        if (arr.length == 0) return result;

        int candidate1 = 0, candidate2 = 1, count1 = 0, count2 = 0;

        for (int num : arr) {
            if (num == candidate1) count1++;
            else if (num == candidate2) count2++;
            else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        count1 = count2 = 0;
        for (int num : arr) {
            if (num == candidate1) count1++;
            else if (num == candidate2) count2++;
        }

        if (count1 > arr.length / 3) result.add(candidate1);
        if (count2 > arr.length / 3 && candidate1 != candidate2) result.add(candidate2);

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 3};
        System.out.println("Majority Elements: " + findMajorityElements(arr));
    }
}

function majorityElements(arr) {
    if (!arr.length) return [];

    let candidate1 = null, candidate2 = null;
    let count1 = 0, count2 = 0;

    for (let num of arr) {
        if (num === candidate1) count1++;
        else if (num === candidate2) count2++;
        else if (count1 === 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 === 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }

    const result = [];
    let n = arr.length;
    if (arr.filter(x => x === candidate1).length > Math.floor(n / 3)) result.push(candidate1);
    if (candidate2 !== candidate1 && arr.filter(x => x === candidate2).length > Math.floor(n / 3)) result.push(candidate2);

    return result;
}

const arr = [3, 2, 3];
console.log("Majority Elements:", majorityElements(arr));

package main

import (
    "fmt"
)

func majorityElements(arr []int) []int {
    var candidate1, candidate2, count1, count2 int
    candidate1, candidate2 = 0, 1

    for _, num := range arr {
        if num == candidate1 {
            count1++
        } else if num == candidate2 {
            count2++
        } else if count1 == 0 {
            candidate1 = num
            count1 = 1
        } else if count2 == 0 {
            candidate2 = num
            count2 = 1
        } else {
            count1--
            count2--
        }
    }

    count1, count2 = 0, 0
    for _, num := range arr {
        if num == candidate1 {
            count1++
        } else if num == candidate2 {
            count2++
        }
    }

    result := []int{}
    if count1 > len(arr)/3 {
        result = append(result, candidate1)
    }
    if count2 > len(arr)/3 && candidate1 != candidate2 {
        result = append(result, candidate2)
    }
    return result
}

func main() {
    arr := []int{3, 2, 3}
    fmt.Println("Majority Elements:", majorityElements(arr))
}

fn majority_elements(arr: Vec<i32>) -> Vec<i32> {
    let mut candidate1 = 0;
    let mut candidate2 = 1;
    let mut count1 = 0;
    let mut count2 = 0;

    for &num in &arr {
        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 &arr {
        if num == candidate1 {
            count1 += 1;
        } else if num == candidate2 {
            count2 += 1;
        }
    }

    let mut result = vec![];
    if count1 > arr.len() / 3 {
        result.push(candidate1);
    }
    if count2 > arr.len() / 3 && candidate1 != candidate2 {
        result.push(candidate2);
    }

    result
}

fn main() {
    let arr = vec![3, 2, 3];
    println!("Majority Elements: {:?}", majority_elements(arr));
}

fun majorityElements(arr: IntArray): List<Int> {
    var candidate1 = 0
    var candidate2 = 1
    var count1 = 0
    var count2 = 0

    for (num in arr) {
        when {
            num == candidate1 -> count1++
            num == candidate2 -> count2++
            count1 == 0 -> {
                candidate1 = num
                count1 = 1
            }
            count2 == 0 -> {
                candidate2 = num
                count2 = 1
            }
            else -> {
                count1--
                count2--
            }
        }
    }

    count1 = 0
    count2 = 0
    for (num in arr) {
        if (num == candidate1) count1++
        else if (num == candidate2) count2++
    }

    val result = mutableListOf<Int>()
    if (count1 > arr.size / 3) result.add(candidate1)
    if (count2 > arr.size / 3 && candidate1 != candidate2) result.add(candidate2)
    return result
}

fun main() {
    val arr = intArrayOf(3, 2, 3)
    println("Majority Elements: ${majorityElements(arr)}")
}

function majorityElements(arr: number[]): number[] {
    if (!arr.length) return [];

    let candidate1: number | null = null;
    let candidate2: number | null = null;
    let count1 = 0, count2 = 0;

    for (let num of arr) {
        if (num === candidate1) count1++;
        else if (num === candidate2) count2++;
        else if (count1 === 0) {
            candidate1 = num;
            count1 = 1;
        } else if (count2 === 0) {
            candidate2 = num;
            count2 = 1;
        } else {
            count1--;
            count2--;
        }
    }

    let result: number[] = [];
    const n = arr.length;
    if (arr.filter(x => x === candidate1).length > Math.floor(n / 3)) result.push(candidate1!);
    if (candidate2 !== candidate1 && arr.filter(x => x === candidate2).length > Math.floor(n / 3)) result.push(candidate2!);

    return result;
}

const arr = [3, 2, 3];
console.log("Majority Elements:", majorityElements(arr));

Time complexity

Space complexity

O(1)

Only a fixed number of variables are used (two candidates and their counts), independent of the input size.