4. Majority Element · DSA Practice

The majority element appears more than ⌊n / 2⌋ times and always exists. Return it, ideally in O(n) time and O(1) extra space.

Example 1

Input: nums = [3,1,3]

Output: 3

Example 2

Input: nums = [6,5,5]

Output: 5

Hint 1

Pair up each majority vote with a different vote and cancel them. What survives?

ArrayCounting

Approach 1: Hash map count

Count everything and return the value with count > n/2.

⏱ Time O(n)💾 Space O(n)

Approach 2: Boyer–Moore voting ✅

Keep a candidate and a vote counter; different values cancel votes. The majority always survives.

⏱ Time O(n)💾 Space O(1)

Reference solution for Boyer–Moore voting (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cand, votes = None, 0       # Boyer-Moore voting
        for x in nums:
            if votes == 0:
                cand = x
            votes += 1 if x == cand else -1
        return cand

class Solution {
    public int majorityElement(int[] nums) {
        int cand = 0, votes = 0;   // Boyer-Moore voting
        for (int x : nums) {
            if (votes == 0) cand = x;
            votes += (x == cand) ? 1 : -1;
        }
        return cand;
    }
}

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cand = 0, votes = 0;   // Boyer-Moore voting
        for (int x : nums) {
            if (votes == 0) cand = x;
            votes += (x == cand) ? 1 : -1;
        }
        return cand;
    }
};

function majorityElement(nums) {
  let cand = null, votes = 0; // Boyer-Moore voting
  for (const x of nums) {
    if (votes === 0) cand = x;
    votes += x === cand ? 1 : -1;
  }
  return cand;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

This problem is explained in the lesson Arrays, Hashing & Prefix Sums.