Majority Element Problem Solution

The majority element problem requires identifying the element that appears more than ⌊n/2⌋ times in an array. This classic algorithmic challenge can be efficiently solved using the Boyer-Moore Voting Algorithm, which provides optimal time and space complexity for large datasets.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the expected size of the input array? (e.g., up to 10^6 elements)
2. Are duplicates allowed in the input array?
3. What should be returned if there are multiple majority elements?
4. Can we modify the input array in-place?
5. What is the target time complexity for the follow-up? (e.g., O(n) time and O(1) space)

Restated problem: Given an array of integers, find the element that appears more than ⌊n/2⌋ times, where n is the size of the array. The problem guarantees that such an element exists.

Input/output specification:

• Input: An integer array nums of length n (1 ≤ n ≤ 5 * 10^4)
• Output: The majority element (an integer that appears more than n/2 times)

Constraints and assumptions:

• The majority element always exists in the input
• The array contains at least one element
• We can assume the majority element is unique (as per problem constraints)
• The input array may be mutated if desired

Data shape and hidden structure: The problem has a mathematical property where:

• If an element appears more than n/2 times, it must occupy at least one position in the middle of a sorted array
• This creates a "majority" invariant that can be exploited using various algorithms
• The constraint guarantees that there's always exactly one such element, so we don't need to handle ties or multiple candidates

The key insight is that we're looking for a specific mathematical property (frequency > n/2) rather than just finding any frequent element, which allows us to use specialized algorithms like Boyer-Moore Majority Vote Algorithm.

2. Pattern Recognition

The most likely pattern here is Voting Algorithm / Boyer-Moore Majority Vote.

The wording that signals this pattern includes:

• "Majority element" - the problem explicitly asks for an element that appears more than n/2 times
• The constraint that a majority element always exists in the input (this is a key signal)
• The requirement for O(n) time and O(1) space complexity

This problem fits the voting pattern because:

• It's asking for a specific element with a mathematical guarantee (more than n/2 occurrences)
• The constraint that majority element always exists allows us to use a "voting" approach where we can cancel out elements
• The problem structure suggests we don't need to count all occurrences, just identify one element that meets the criteria

The core insight is that if we have a majority element, it will always be the final remaining candidate after we "cancel out" pairs of different elements. This is because a majority element appears more than n/2 times, so even if we pair it with every other element, it will still have at least one "vote" remaining.

This pattern is also commonly seen in problems like:

• Finding the element that appears more than n/3 times (requires two counters)
• Problems where we can eliminate candidates based on some property
• When there's a mathematical guarantee about the existence of a specific element

The key insight is that we don't need to count frequencies - we just need to find one element that appears more than n/2 times, which can be solved with a single pass and constant space using the voting algorithm.

3. Approach Evolution

My first instinct is to use a brute force approach where I count occurrences of each element using a HashMap, which would be O(n²) in the worst case because for each element, I'd need to scan the entire array to count occurrences. But that's inefficient and not optimal.

Let me think about how to optimize this. I notice that if I sort the array first, then the majority element will always be at the middle position since it appears more than n/2 times. This reduces it to O(n log n) because sorting dominates the complexity.

But wait, there's an even better approach - Boyer-Moore Majority Vote Algorithm. This algorithm works on the principle that if we maintain a candidate and a counter, when we see the same element as our candidate, we increment the counter, otherwise we decrement it. When the counter reaches zero, we pick a new candidate.

The key insight is that if an element appears more than n/2 times, it will survive all the canceling operations and remain as our final candidate. This is O(n) time and O(1) space, which is optimal for this problem.

Let me trace through the logic:

• We maintain a candidate and a count
• Initially, we set the first element as candidate and count = 1
• For each subsequent element:
  • If it matches our candidate, increment count
  • If it doesn't match, decrement count
  • When count reaches zero, we switch candidate to current element and reset count to 1
• The final candidate will be our majority element

This approach works because the majority element appears more than n/2 times, so even if all other elements cancel it out in pairs, it will still have a positive count at the end.

The invariant that must hold is: if there's a majority element, it will be the final candidate returned by this algorithm.

4. Data Structure Choice

For this majority element problem, I'll use a HashMap to track element frequencies.

The HashMap is the primary data structure because:

• It allows O(1) average-time lookups and updates
• It naturally handles the frequency counting requirement
• It's well-suited for tracking element occurrences in a single pass

The HashMap stores <Integer, Integer> pairs where:

• Key: The element value from the input array
• Value: The count of that element seen so far

I'm choosing HashMap over other structures like:

• Array-based counting: Would require knowing the range of input values (which we don't)
• TreeSet/HashSet: Don't provide frequency tracking capability
• Custom hash table: Overkill when standard library is sufficient

The space complexity will be O(k) where k is the number of distinct elements, which in worst case is O(n). This is acceptable since we're not trying to optimize space beyond what's necessary for the algorithm.

The HashMap also serves as a helper structure that simplifies the implementation by abstracting away the counting logic, making the code cleaner and more readable than manual array-based counting or nested loops.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works.

Example: nums = [3, 2, 3]

Step-by-step execution:

1. Initialization: candidate = 3, count = 1

   • First element is 3, so we set candidate to 3 and count to 1

2. Iteration 1 (i = 1, nums[i] = 2):

   • Current element (2) ≠ candidate (3)
   • Count > 0, so we decrement count: count = 0
   • Since count reached 0, we update candidate to current element: candidate = 2

3. Iteration 2 (i = 2, nums[i] = 3):

   • Current element (3) ≠ candidate (2)
   • Count > 0, so we decrement count: count = -1
   • Since count reached 0, we update candidate to current element: candidate = 3

4. Final result: candidate = 3

Key insights during trace:

• The algorithm maintains the invariant that if a majority element exists, it will be the final candidate
• When count reaches 0, we're essentially "resetting" our vote for the next potential majority element
• The final candidate must be a majority element due to the problem guarantee

Edge case handling:

• If we had [2, 2, 1, 1], the algorithm would still find candidate 2
• The algorithm correctly handles the case where majority element appears at end of array
• It works regardless of whether we process elements in order or encounter the majority element late

The algorithm terminates correctly because:

1. We process each element exactly once
2. The candidate variable always represents a potential majority element
3. When count becomes 0, we know the current candidate isn't the majority in the prefix processed so far
4. The final candidate must be majority due to problem constraints

6. Java Solution

public class MajorityElement {
    /**
     * Finds the majority element in an array using Boyer-Moore Voting Algorithm.
     * The majority element appears more than n/2 times where n is array length.
     * 
     * @param nums input array of integers
     * @return the majority element
     */
    public int majorityElement(int[] nums) {
        // Initialize candidate and count
        int candidate = 0;
        int count = 0;
        
        // Phase 1: Find candidate using Boyer-Moore Voting Algorithm
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            
            // Increment or decrement count based on match
            count += (num == candidate) ? 1 : -1;
        }
        
        // Phase 2: Verify the candidate is actually majority element
        // (This step can be skipped if problem guarantees a majority exists)
        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }
        
        // Return candidate if it's indeed majority (should always be true per problem constraints)
        return count > nums.length / 2 ? candidate : -1;
    }
}

The solution implements the Boyer-Moore Voting Algorithm which is optimal for this problem. The approach uses two phases: first finding a candidate element that could potentially be the majority, then verifying it's actually the majority element. The algorithm maintains a running count that effectively cancels out non-majority elements, ensuring the final candidate must be the majority element when one exists.

7. Complexity Analysis

Time Complexity: O(n)

• The algorithm makes a single pass through the input array with constant-time operations at each step
• Each element is processed exactly once, and all operations (comparisons, updates) are O(1)
• Therefore, the overall time complexity is linear

Space Complexity: O(1)

• The solution uses only a constant amount of extra space regardless of input size
• Only two variables (candidate and count) are maintained throughout the execution
• No additional data structures like hash maps, arrays, or stacks are required
• The space usage remains bounded by a constant factor

Why these bounds are correct: The linear time complexity is optimal for this problem since we must examine each element at least once to determine the majority element. The constant space complexity is achieved by leveraging the Boyer-Moore Majority Vote algorithm's key insight that a majority element appears more than n/2 times, allowing us to cancel out non-majority elements without needing to count frequencies explicitly.

This solution is optimal because:

1. We cannot solve this problem faster than O(n) time since we must inspect all elements
2. We cannot use less than O(1) space since we need to track only the current candidate and its count
3. The algorithm is deterministic and handles all valid inputs correctly

The solution achieves the theoretical lower bounds for this problem, making it both time and space optimal.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Should handle gracefully, though problem constraints typically assume valid input with at least one element
• Single element array: The only element is automatically the majority element (appears n/2 + 1 times)
• Two-element array: If both elements are same, that's the majority; if different, the problem constraints guarantee one appears more than half the time

Duplicate Values and Repeated States

• Multiple elements at majority threshold: The problem guarantees exactly one majority element, so we don't need to handle ties
• All elements equal: Trivial case where every element is the majority element (though constraint ensures only one answer)
• Duplicate counting: In algorithms like Boyer-Moore, we must ensure proper vote tracking to avoid incorrect cancellation

Boundary Conditions

• Array size at minimum valid: With n = 1, element appears 1 time (1/2 + 1 = 1.5, so 1 is valid)
• Array size at maximum: For large arrays, ensure integer overflow isn't an issue in vote counting (though not a practical concern for standard integer types)
• Majority threshold edge case: When n = 2, majority requires 2/2 + 1 = 2 elements (all must be same)

Common Implementation Mistakes

• Incorrect threshold calculation: Using n/2 instead of n/2 + 1 for majority threshold (e.g., for n=3, majority requires 2+1=3 elements)
• Boyer-Moore vote reset: Incorrectly resetting candidate or count when votes become zero
• Off-by-one errors in counting: Miscounting elements during vote accumulation
• Not handling the final candidate properly: In Boyer-Moore, we must verify that the final candidate actually meets majority criteria (though problem guarantees one exists)
• Integer overflow in vote counting: Though unlikely with standard integer types, could be an issue in constrained environments

The solution must ensure that the final candidate is indeed majority (though problem constraints guarantee this), and handle all edge cases in the counting logic carefully.

9. Alternative Approaches

There are several alternative approaches to solving the majority element problem, each with different trade-offs:

HashMap Approach: Use a HashMap to count occurrences of each element. This is O(n) time and O(n) space. While simpler to implement, it uses extra space proportional to the number of unique elements.

Sorting Approach: Sort the array first, then check if the element at index n/2 (for odd-length arrays) or n/2 and n/2-1 (for even-length arrays) is the majority element. This is O(n log n) time and O(1) space if sorting in-place, or O(n) space if using a copy. The sorting approach is simpler conceptually but less efficient.

Divide and Conquer: Recursively divide the array into halves, find majority elements in each half, then combine results. This is O(n log n) time and O(log n) space due to recursion stack. More complex to implement correctly.

Boyer-Moore Voting Algorithm (our chosen solution): This is optimal with O(n) time and O(1) space. It's specifically designed for this problem and is the most efficient approach.

The Boyer-Moore Voting Algorithm is preferred because it's both time and space optimal, requires no extra data structures, and works under the assumption that a majority element exists (which is guaranteed by the problem constraints). The alternatives either use more space or have worse time complexity, making them less suitable for large inputs.

10. Test Cases

public class MajorityElementTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic case with majority element
        int[] nums1 = {3, 2, 3};
        // Expected: 3
        System.out.println("Test 1 - Basic majority element: " + 
                          new Solution().majorityElement(nums1));
        
        // Test case 2: Array with multiple elements, one majority
        int[] nums2 = {2, 2, 1, 1, 1, 2, 2};
        // Expected: 2
        System.out.println("Test 2 - Majority element appears more than n/2 times: " + 
                          new Solution().majorityElement(nums2));
        
        // Test case 3: Single element array
        int[] nums3 = {5};
        // Expected: 5
        System.out.println("Test 3 - Single element array: " + 
                          new Solution().majorityElement(nums3));
        
        // Test case 4: Two elements, one majority
        int[] nums4 = {1, 1, 2, 2, 2};
        // Expected: 2
        System.out.println("Test 4 - Two elements with majority: " + 
                          new Solution().majorityElement(nums4));
        
        // Test case 5: Empty array (edge case)
        int[] nums5 = {};
        // Expected: -1 or throw exception depending on implementation
        try {
            System.out.println("Test 5 - Empty array: " + 
                              new Solution().majorityElement(nums5));
        } catch (Exception e) {
            System.out.println("Test 5 - Empty array throws: " + e.getClass().getSimpleName());
        }
        
        // Test case 6: Array with all same elements
        int[] nums6 = {7, 7, 7, 7, 7};
        // Expected: 7
        System.out.println("Test 6 - All same elements: " + 
                          new Solution().majorityElement(nums6));
        
        // Test case 7: Large array with majority element at end
        int[] nums7 = new int[1000];
        for (int i = 0; i < 1000; i++) {
            nums7[i] = (i < 501) ? 1 : 2;
        }
        // Expected: 1 (since 501 > 1000/2)
        System.out.println("Test 7 - Large array majority at beginning: " + 
                          new Solution().majorityElement(nums7));
    }
}

Sample Test Cases:

1. Basic case: [3, 2, 3] → Expected: 3
2. Multiple elements: [2, 2, 1, 1, 1, 2, 2] → Expected: 2
3. Single element: [5] → Expected: 5
4. Two elements: [1, 1, 2, 2, 2] → Expected: 2
5. Empty array: [] → Expected: Exception or -1
6. All same elements: [7, 7, 7, 7, 7] → Expected: 7
7. Large array: [1, 1, ..., 1, 2, 2, ... 2] where majority is 1 → Expected: 1

Tricky Cases:

• Arrays with exactly n/2 elements (edge case for majority requirement)
• Arrays where majority element appears at boundary positions
• Large arrays that stress performance constraints

Boundary Cases:

• Minimum valid input size (n = 1)
• Maximum valid input size (as constrained by problem)
• Arrays with duplicate majority elements
• Arrays where no element appears more than n/2 times (should not occur in valid inputs)

11. Final Summary

The core insight is that if an element appears more than n/2 times in an array of size n, it must occupy the middle position when the array is sorted. This allows us to solve the problem in O(n log n) time by sorting and checking the middle element, or optimally in O(n) time using Boyer-Moore Voting Algorithm.

The solution works because the majority element's frequency exceeds half the array size, making it impossible for any other element to occupy the middle position in a sorted array. This approach is optimal in both time and space complexity for the given constraints, with O(n) time and O(1) space for the voting algorithm variant.

What makes this solution efficient is leveraging the mathematical property of majority elements and avoiding unnecessary counting operations through sorting or voting mechanisms, rather than maintaining frequency counts for all elements.