Majority Element

Time: O(n)

Space: O(1)

Intuition

Boyer-Moore Voting Algorithm: the majority element (appears > n/2 times) will survive cancellation. Maintain a candidate and counter; increment for matching, decrement for non-matching; when counter reaches 0, switch candidate.

Algorithm

1candidate = arr[0], count = 1.
2For i from 1 to nâˆ’1: if arr[i]==candidate: count++. Else: count--. If count==0: candidate=arr[i], count=1.
3Return candidate.

Example Walkthrough

Input: arr = [3,3,4,2,4,4,2,4,4]

1.3(1),3(2),4(1),2(0)â†’4(1),4(2),2(1),4(2),4(3). Candidate=4.

Output: 4

Common Pitfalls

•The problem guarantees a majority element exists â€” no verification step needed. If not guaranteed, verify by counting.

Majority Element.java

Java

// Approach: Boyer-Moore voting algorithm. One pass maintaining candidate and count.
// Time: O(n) Space: O(1)
class Solution {
    static int majorityElement(int arr[]) {
        int cnt = 0;
        int ele = -1;
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            if (cnt == 0) {
                cnt = 1;
                ele = arr[i];
            } else if (arr[i] == ele)
                cnt++;
            else
                cnt--;
        }

        int cnt1 = 0;
        for (int i = 0; i < n; i++) {
            if (ele == arr[i])
                cnt1++;
        }

        if (cnt1 > n / 2)
            return ele;
        return -1;
    }
}

Was this solution helpful?