☕ DSA Java Articles

Topics › Arrays › Medium

Majority Element-I

Easy TUF ID 22 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an integer array nums of length n. The majority element is a value that appears strictly more than n / 2 times (integer division). Return it. The LeetCode version guarantees that a majority element always exists; the version here returns -1 when there is none, which costs one extra verification pass and makes the solution usable on arbitrary input.

Note the word “strictly”: in [1, 1, 2, 2] the value 1 appears exactly n / 2 = 2 times, which is not a majority. There can be at most one majority element, because two values each appearing more than half the time would need more than n elements.

Constraints: 0 ≤ n ≤ 5 × 10^4, values fit in a 32-bit signed integer.

Example 1

nums = [3, 2, 3]
answer = 3          // 3 appears 2 times, 2 > 3/2 = 1

Example 2

nums = [2, 2, 1, 1, 1, 2, 2]
answer = 2          // 2 appears 4 times, 4 > 7/2 = 3

Example 3

nums = [1, 2, 3]
answer = -1         // nothing appears more than once

Approach 1: Brute force

Intuition. For every element, count how many times its value occurs in the whole array and compare with n / 2. The first element that passes is the answer.

Algorithm.

  1. For every index i:
  2. Count indices j with nums[j] == nums[i].
  3. If count > n / 2, return nums[i].
  4. Return -1.
static int bruteForce(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (nums[j] == nums[i]) count++;
        }
        if (count > n / 2) return nums[i];
    }
    return -1;
}

Complexity. Time O(n^2): each element triggers a full scan. Space O(1).

Approach 2: Better, a frequency map

Intuition. Count all values in one pass with a hash map instead of re-scanning. As soon as some value’s count exceeds n / 2 we can stop; it cannot be beaten. If the loop finishes, no value made it.

Algorithm.

  1. Create an empty map freq.
  2. For every x: increment freq[x]; if the new count is > n / 2, return x.
  3. Return -1.
static int better(int[] nums) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) {
        int c = freq.merge(x, 1, Integer::sum);
        if (c > nums.length / 2) return x;
    }
    return -1;
}

Complexity. Time O(n) on average. Space O(n): in the worst case (no majority) the map holds every distinct value.

A second “better” option worth knowing: sort and look at the middle. If a majority exists, it occupies more than half of the sorted array, so it must cover the middle index n / 2. That is O(n log n) time and, if sorting in place is allowed, O(1) extra space. You still need a counting pass to confirm the candidate when a majority is not guaranteed.

Approach 3: Optimal, Boyer-Moore voting

Intuition. Imagine every occurrence of the majority element as a vote for it and every other element as a vote against. Because the majority has more than half the elements, even if every other element cancels one majority vote, at least one majority vote survives. Boyer-Moore turns this into an algorithm with two variables: a candidate and a votes counter.

Walk the array. If votes is 0, adopt the current element as the candidate with one vote. Otherwise, if the element equals the candidate, add a vote; if it differs, remove one. Whenever votes drops to 0, the segment just finished contained the candidate exactly as many times as all other values combined, so throwing that segment away removes equally many majority and non-majority elements. The majority element is still the majority of what remains. By induction, the candidate at the end is the only value that can be the majority.

That last word is important: if no majority exists, the algorithm still ends with some candidate. So we count its occurrences in a second pass and return -1 if it falls short. When the problem guarantees a majority, this pass can be skipped.

Algorithm.

  1. Set candidate = 0, votes = 0.
  2. For every x:
    • if votes == 0: candidate = x, votes = 1;
    • else if x == candidate: votes++;
    • else: votes--.
  3. Count how many times candidate occurs. Return it if the count is > n / 2, else -1.
static int optimal(int[] nums) {
    int candidate = 0, votes = 0;
    for (int x : nums) {
        if (votes == 0) {
            candidate = x;
            votes = 1;
        } else if (x == candidate) {
            votes++;
        } else {
            votes--;
        }
    }
    int count = 0;
    for (int x : nums) if (x == candidate) count++;
    return count > nums.length / 2 ? candidate : -1;
}

Dry run on nums = [2, 2, 1, 1, 1, 2, 2]:

x votes before action candidate votes after
2 0 adopt 2 2 1
2 1 same, +1 2 2
1 2 differs, -1 2 1
1 1 differs, -1 2 0
1 0 adopt 1 1 1
2 1 differs, -1 1 0
2 0 adopt 2 2 1

The candidate is 2; the verification pass counts four occurrences, 4 > 3, so return 2. Notice that the candidate was briefly 1 in the middle; the algorithm does not need the candidate to be right at every step, only at the end.

Complexity. Time O(n): two passes. Space O(1): two integers.

Why does cancellation preserve the majority? Suppose the majority value m occurs c > n / 2 times. Each time votes returns to 0 after a segment of length L, that segment contained exactly L / 2 copies of the then-candidate and L / 2 other elements. Whether or not the candidate was m, at most L / 2 copies of m were in the segment, so after discarding it m still has more than half of the remaining elements. The final segment (where votes ends positive) is therefore dominated by m, and its candidate is m.

Edge cases and pitfalls