Majority Element

Element appearing more than n/2 times. [2,2,3,3,1,2,2] → 2 (appears 4 times, n/2 = 3). (LeetCode 169, LeetCode 229)

Brute force: count each element’s occurrences via nested loops — O(n²).

Better — hashmap: count frequencies in one pass, then scan the map for a count exceeding n/2 — O(n) time, O(n) space.

Optimal — Moore’s Voting Algorithm: track a potential majority element (pme) and a vote count. Walk the array: if count == 0, adopt the current element as pme and set count = 1; if the current element matches pme, increment count; otherwise decrement it. If a genuine majority element exists, it survives this process as pme. Afterward, verify by counting pme’s actual occurrences.

public int majorityElement(int[] nums) {
    int pme = 0;
    int count = 0;

    // Step 1: Find the majority candidate
    for(int i = 0; i < nums.length; i++) {
        if(count == 0) {
            pme = nums[i];
            count = 1;
        } else if(nums[i] == pme) {
            count++;
        } else {
            count--;
        }
    }

    // Step 2: Validate the candidate
    int vCount = 0;
    for(int i = 0; i < nums.length; i++) {
        if(nums[i] == pme) vCount++;
    }

    if(vCount > nums.length / 2) {
        return pme;
    }

    return -1;
}

Time: O(n) — two passes. Space: O(1).