Majority Element

Given an array where one element appears more than n/2 times, return that element.

EasyRecommendedBoyer-Moore VotingLeetCode

Why solve this?

Boyer-Moore voting solves it in O(1) space where a hash-map count would use O(n) — a good lesson in exploiting a problem's guarantees.

Pattern recognition

A guaranteed strict-majority element (more than half the array) can always be found with a running candidate + counter, not a full frequency count.

Prerequisites

Arrays
Hashing

Hints

A hash map of counts works but uses O(n) extra space — can you do O(1)?
Keep a 'current candidate' and a counter; increment when you see the candidate again, decrement otherwise.
When the counter hits zero, the next element becomes the new candidate.

Approach

Boyer-Moore voting: track a `candidate` and a `count`. For each number, if `count == 0`, set it as the new candidate. Increment `count` if the number equals `candidate`, otherwise decrement. Because the true majority element appears more than n/2 times, it always survives as the final candidate.

Java solution

Solution.java

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

Time: O(n)Space: O(1)