1. Understanding the Problem

You are given an array nums of size n. Your task is to return the majority element.

The majority element is defined as the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

The Core Constraint (The Trap):

While counting occurrences using a dictionary or hash map is easy, the problem challenges us to solve it in linear time and O(1) space. Storing frequencies of thousands of distinct numbers will pass test cases, but it fails the optimal space benchmark expected in top-tier technical interviews.

2. The Naive Approach: Hash Map Frequency Counting

The most intuitive way to solve this is to iterate through the array and store the count of every number inside a Hash Map (or Dictionary). Once you find a number whose frequency exceeds n / 2, you return it.

Trade-off Analysis

While this logic is sound and easy to implement, it comes with a memory tradeoff:

• Time Complexity: O(N) — You traverse the array once, performing O(1) Hash Map updates.
• Space Complexity: O(N) — In the worst-case scenario (many unique elements before the majority element appears), you store up to N/2 distinct keys inside your Hash Map.

3. The Optimal Approach: Boyer-Moore Voting Algorithm (O(1) Space)

To pass a senior-level technical interview, we want to achieve an O(1) space complexity. We can do this without tracking every element's history by using the famous Boyer-Moore Voting Algorithm.

Imagine a political election where every candidate's supporters vote to cancel out the vote of an opposing candidate. If one candidate has more than 50% of the total population, even if every single other person in the country teams up to vote against them, the majority candidate will still have at least one vote remaining at the end!

We apply this exact logic to our array. We maintain a single candidate variable and a count tracker. When the count drops to 0, we select a new candidate. Matching elements increment the count, while non-matching elements decrement it.

4. The Logic Step-by-Step

1. Initialize a variable candidate to keep track of our current majority guess.
2. Initialize a variable count = 0 to track the candidate's net popularity.
3. Traverse the Array: For each number in nums:
   • If count == 0, assign the current number as our new candidate.
   • If the current number matches candidate, increment count by 1 (count += 1).
   • If the current number does not match candidate, decrement count by 1 (count -= 1).
4. When the loop finishes, the candidate variable is guaranteed to hold the majority element. Return candidate.

5. Complexity Analysis

• Time Complexity: O(N) — We scan the array exactly once from start to finish.
• Space Complexity: O(1) — We only store two scalar variables (candidate and count), regardless of how large the array grows. Memory remains strictly constant!

6. Code Implementations

Expand the sections below to see the optimal O(1) space "Boyer-Moore" implementations across different languages.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None
        count = 0
        
        for num in nums:
            # If our vote count hits 0, pick a new candidate
            if count == 0:
                candidate = num
                
            # Increment if matching candidate, decrement otherwise
            if num == candidate:
                count += 1
            else:
                count -= 1
                
        return candidate

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        
        for (int num : nums) {
            // Reset candidate when counter reaches zero
            if (count == 0) {
                candidate = num;
            }
            
            // Cancel out votes
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        return candidate;
    }
}

#include <vector>

class Solution {
public:
    int majorityElement(std::vector<int>&nums) {
        int candidate = 0;
        int count = 0;
        
        for (int num : nums) {
            // Select new candidate if current count is exhausted
            if (count == 0) {
                candidate = num;
            }
            
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        return candidate;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just mastered the Boyer-Moore Voting Algorithm! This problem beautifully illustrates that knowing mathematical properties (like an element making up > 50% of an array) allows you to bypass heavy memory allocation entirely. By replacing an O(N) Hash Map with a simple cancellation mechanism, you demonstrated senior-level algorithmic efficiency. Keep this "cancellation pairing" mental model in your toolkit—it is a game-changer for frequency-based array challenges!