Majority Element – 169. LeetCode

The Majority Element problem asks you to find the element that appears more than n/2 times in an array of size n. This element is guaranteed to exist. For example, in the array [3, 3, 4, 2, 3, 3, 5, 3], the majority element is 3 because it appears more than half the time. The challenge is to solve this efficiently.

Brute Force Approach

The brute force solution involves checking the count of each element and determining which element appears the most times.

import java.util.HashMap;

public class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> countMap = new HashMap<>();
        int majorityCount = nums.length / 2;

        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
            if (countMap.get(num) > majorityCount) {
                return num;
            }
        }
        return -1; // This case won't occur as per the problem statement.
    }
}

• Use a hash map to count the occurences of each element.
• For every element, chick if its count exceeds n/2.
• If yes, return that element.

Optimal Solution: Boyer-Moore Voting Algorithm

Key Idea:

The Boyer-Moore Voting Algorithm is a clever way to find the majority element using constant space and a single traversal of the array. It works by maintaining a candidate for the majority element and a count. As you iterate through the array:

• If the count is zero, pick the current element as the candidate.

• If the count is non-zero:

• Increment the count if the current element matches the candidate.

• Decrement the count if it does not.

Algorithm Steps:

1. Initialize candidate to any value and count to 0.

2. Traverse the array:

• If count == 0, set the current element as the candidate and increment the count.

• If the current element matches the candidate, increment the count.

• If the current element does not match the candidate, decrement the count.

3. After the loop, the candidate holds the majority element.

public class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0]; // Potential majority element
        int count = 0;           // Counter for votes

        // Traverse the array to determine the candidate
        for (int num : nums) {
            if (count == 0) {    // Reset candidate if count is 0
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1; // Increment or decrement count
        }

        return candidate; // The candidate is the majority element
    }
}

Line-By-Line Explanation

Step 1: Initialize Variables

int candidate = nums[0]; // Potential majority element
int count = 0;           // Counter for votes

• The candidate represents the current potential majority element. It will be updated as we iterate through the array.
• count helps determine if the current candidate is valid or if we need to choose a new one.

Step 2: Traverse the Array

for (int num : nums) {

• To evaluate all elements in the array and find the majority element.

Step 3: Reset Candidate When count == 0

if (count == 0) {
    candidate = num;
}

• The algorithm resets the candidate when there’s no confidence in the current majority (count == 0).

Step 4: Update the Count

count += (num == candidate) ? 1 : -1;

• Incrementing the count when there’s a match reinforces confidence in the candidate.
• Decrementing the count where there’s no match ensures other elements are considered fairly, balancing votes.

Step 5: Return

return candidate;

• After the loop completes, returns the candidate as the majority element.

Why This Code Works

1. Optimal Time Complexity:

• The algorithm traverses the array once (O(n)) and performs constant-time operations for each element.

2. Optimal Space Complexity:

• Only two variables (candidate and count) are used, resulting in O(1) space complexity.

3. Clarity:

• The code is simple and easy to follow, avoiding unnecessary data structures or complex logic.

4. Adherence to Problem Constraints:

• The problem guarantees the existence of a majority element, allowing this solution to work without additional checks.

This code is an implementation of the Boyer-Moore Voting Algorithm, a highly efficient solution to the Majority Element problem. It uses a simple voting mechanism to track the majority element in O(n) time and O(1) space. By balancing votes dynamically, it ensures correctness while keeping the implementation clean and optimal.