Find majority element

Problem Statement

Given an array of n elements, find the majority element. The majority element is the element that appears more than ⌊n/2⌋ times.

Constraints:

• You may assume the majority element always exists in the array
• Array has at least one element

Example:

• Input: arr = [3, 2, 3]
• Output: 3
• Explanation: 3 appears 2 times, which is > 3/2 = 1

Example 2:

• Input: arr = [2, 2, 1, 1, 1, 2, 2]
• Output: 2
• Explanation: 2 appears 4 times, which is > 7/2 = 3

Approach 1: Brute Force (Count Each Element)

Intuition

For each element, count its occurrences. If count exceeds n/2, it's the majority element.

Algorithm

1. For each element in the array
2. Count its total occurrences
3. If count > n/2, return that element

public class Solution {
    public int majorityElement(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; // No majority element
    }
}

Complexity Analysis

• Time Complexity: O(n²) - Nested loops
• Space Complexity: O(1) - No extra space

Approach 2: Using HashMap

Intuition

Use a hash map to count occurrences of each element in one pass.

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        int n = nums.length;
        
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
            if (count.get(num) > n / 2) {
                return num;
            }
        }
        
        return -1;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass
• Space Complexity: O(n) - HashMap storage

Approach 3: Sorting

Intuition

If we sort the array, the majority element will always be at the middle index (n/2).

import java.util.Arrays;

public class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

Why This Works

Complexity Analysis

• Time Complexity: O(n log n) - Sorting
• Space Complexity: O(1) or O(n) - Depends on sorting algorithm

Approach 4: Moore's Voting Algorithm (Optimal)

Intuition

The majority element will "survive" even if we cancel out pairs of different elements. We maintain a candidate and a count. When count becomes 0, we pick a new candidate.

Algorithm

1. Initialize candidate = first element, count = 1
2. Traverse the array:
   • If count is 0, set current element as candidate
   • If current element equals candidate, increment count
   • Else decrement count
3. Verify the candidate (optional if majority guaranteed)

Why This Works:

• The majority element appears > n/2 times
• Even if all other elements "vote against" it, it will still have positive votes
• Non-majority elements will eventually cancel each other out

public class Solution {
    public int majorityElement(int[] nums) {
        // Phase 1: Find candidate
        int candidate = nums[0];
        int count = 1;
        
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            } else if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        // Phase 2: Verify candidate (if majority not guaranteed)
        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }
        
        if (count > nums.length / 2) {
            return candidate;
        }
        
        return -1; // No majority element
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n) - Two passes
• Space Complexity: O(1) - Only two variables

Approach 5: Randomization

Intuition

Since majority element appears > n/2 times, picking a random element has > 50% chance of being the majority element.

Complexity Analysis

• Time Complexity: O(n) expected - Each trial is O(n), expected trials is O(1)
• Space Complexity: O(1)

Variation: Majority Element II (n/3)

Find all elements appearing more than ⌊n/3⌋ times. At most 2 such elements can exist.

Key Takeaways

1. Moore's Voting Algorithm: Optimal O(n) time and O(1) space solution
2. Cancellation Principle: Pairs of different elements cancel each other out
3. Verification Step: Always verify if majority not guaranteed to exist
4. Sorting Insight: Majority element always at middle of sorted array
5. Generalization: For n/k majority, maintain k-1 candidates
6. Applications: Elections, consensus algorithms, stream processing