Majority Element

How it works

Since the majority element appears more than n/2 times, any random pick has greater than 50% chance of selecting it. We repeatedly pick a random element and check if it's the majority. On average, we need only about 2 picks to find the answer, making this surprisingly efficient in practice.

Steps

1. Randomly select an element from the array.
2. Count how many times it appears.
3. If the count exceeds n / 2, return it.
4. Otherwise, repeat from step 1.

Complexity

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

The probability of randomly choosing the majority element is greater than 50%, so the expected number of iterations in the outer while loop is constant.

Things to watch for

Using >= Instead of > for the Majority Check

The majority element must appear more than n/2 times, not n/2 or more. Using count >= n/2 instead of count > n/2 can return incorrect results for arrays like [1, 2, 2] where 2 appears exactly n/2 times but is not a strict majority.

Forgetting Integer Division Semantics

In languages like Python 3, / performs floating-point division while // performs integer division. Using n / 2 instead of n // 2 can lead to type errors or incorrect comparisons. Similarly, in JavaScript, Math.floor(n / 2) is needed for proper integer division.

import random

class Solution:
    def majorityElement(self, nums):
        n = len(nums)
        while True:
            candidate = random.choice(nums)
            if nums.count(candidate) > n // 2:
                return candidate

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();

        while (true) {
            int candidate = nums[rand() % n];
            int count = 0;
            for (int num : nums) {
                if (num == candidate) {
                    count++;
                }
            }
            if (count > n / 2) {
                return candidate;
            }
        }
    }
};