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

Given an array of integers, your task is to find the majority element, which is defined as the element that appears more than ⌊n/2⌋ times in the array (where n is the size of the array).

If a majority element exists, return it. If no such element exists, return -1.

This problem assumes that the array may or may not contain a valid majority element.

Understanding the Problem

We are given an array of integers, and our goal is to find the majority element—if it exists. But what exactly is a majority element?

A majority element is an element that appears more than n/2 times in the array, where n is the total number of elements. If no such element exists, we return -1.

Approach to Solve the Problem

Step-by-step Explanation Using an Example

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

Here, n = 6, so to qualify as a majority, an element must appear more than 6/2 = 3 times, i.e., at least 4 times.

• Count of 3 = 5 → meets the condition
• Count of 2 = 1 → does not qualify

So, the answer is 3.

Step-by-step Plan to Solve It

1. Use the Boyer-Moore Voting Algorithm to identify a candidate.
2. Verify if the candidate actually occurs more than n/2 times.
3. If yes, return the candidate; else, return -1.

Intuitive Explanation

Think of it like a voting game. Every time an element agrees with our current "leader", we give it a vote. When it disagrees, we take away a vote. If we run out of votes (count becomes 0), we choose a new leader.

In the end, if there’s a true majority, it will have survived all the challenges and still be the leader.

Edge Cases to Handle

• Empty Array: No elements → return -1
• Single Element: [5] → 5 is the majority (only one element)
• No Majority Element: [1, 2, 3, 4] → all are unique → return -1
• Tie Situation: [1, 1, 2, 2, 3, 3] → no one has > n/2 count → return -1

Why This Works

Because non-majority elements cancel each other out, only the true majority can remain standing after the count balancing. If no such element exists, the second pass will filter it out.

1. Given an array arr of size n.
2. Initialize count = 0 and candidate = None.
3. Traverse the array:
4. → If count == 0, set candidate = current element.
5. → If current element == candidate, increment count, else decrement count.
6. After the loop, candidate is the majority element.
7. (Optional: Verify candidate by counting its actual occurrences if required.)

#include <stdio.h>

int majorityElement(int arr[], int n) {
    int count = 0, candidate = 0;
    for (int i = 0; i < n; i++) {
        if (count == 0) {
            candidate = arr[i];
        }
        count += (arr[i] == candidate) ? 1 : -1;
    }
    return candidate;
}

int main() {
    int arr[] = {2, 2, 1, 1, 1, 2, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Majority Element: %d\n", majorityElement(arr, n));
    return 0;
}

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

int majorityElement(vector<int>& arr) {
    int count = 0, candidate = 0;
    for (int num : arr) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }
    return candidate;
}

int main() {
    vector<int> arr = {2, 2, 1, 1, 1, 2, 2};
    cout << "Majority Element: " << majorityElement(arr) << endl;
    return 0;
}

def majority_element(arr):
    count = 0
    candidate = None

    for num in arr:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)

    return candidate

# Sample Input
arr = [2, 2, 1, 1, 1, 2, 2]
print("Majority Element:", majority_element(arr))

public class MajorityElement {
    public static int findMajorityElement(int[] arr) {
        int count = 0, candidate = 0;
        for (int num : arr) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }

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

function majorityElement(arr) {
    let count = 0;
    let candidate = null;

    for (let num of arr) {
        if (count === 0) {
            candidate = num;
        }
        count += (num === candidate) ? 1 : -1;
    }

    return candidate;
}

// Sample Input
const arr = [2, 2, 1, 1, 1, 2, 2];
console.log("Majority Element:", majorityElement(arr));

package main

import (
    "fmt"
)

func majorityElement(arr []int) int {
    count := 0
    candidate := 0
    for _, num := range arr {
        if count == 0 {
            candidate = num
        }
        if num == candidate {
            count++
        } else {
            count--
        }
    }
    return candidate
}

func main() {
    arr := []int{2, 2, 1, 1, 1, 2, 2}
    fmt.Println("Majority Element:", majorityElement(arr))
}

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

fn main() {
    let arr = vec![2, 2, 1, 1, 1, 2, 2];
    println!("Majority Element: {}", majority_element(&arr));
}

fun majorityElement(arr: IntArray): Int {
    var count = 0
    var candidate = 0
    for (num in arr) {
        if (count == 0) {
            candidate = num
        }
        count += if (num == candidate) 1 else -1
    }
    return candidate
}

fun main() {
    val arr = intArrayOf(2, 2, 1, 1, 1, 2, 2)
    println("Majority Element: ${majorityElement(arr)}")
}

func majorityElement(_ arr: [Int]) -> Int {
    var count = 0
    var candidate = 0
    for num in arr {
        if count == 0 {
            candidate = num
        }
        count += (num == candidate) ? 1 : -1
    }
    return candidate
}

let arr = [2, 2, 1, 1, 1, 2, 2]
print("Majority Element:", majorityElement(arr))

function majorityElement(arr: number[]): number {
    let count = 0;
    let candidate = 0;
    for (const num of arr) {
        if (count === 0) {
            candidate = num;
        }
        count += (num === candidate) ? 1 : -1;
    }
    return candidate;
}

const arr = [2, 2, 1, 1, 1, 2, 2];
console.log("Majority Element:", majorityElement(arr));

Time complexity

Space complexity

O(1)

Only two variables—count and candidate—are used throughout the algorithm, making the space constant.