Problem Description

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

The majority element is defined as the element that appears more than ⌊n / 2⌋ times in the array. In other words, it's an element that occurs more than half the time in the array.

For example:

• In an array of size 7, the majority element must appear at least 4 times
• In an array of size 8, the majority element must appear at least 5 times

The problem guarantees that a majority element always exists in the given array, so you don't need to handle cases where no majority element is present.

The solution implements the Boyer-Moore Voting Algorithm, which is an efficient way to find the majority element in a single pass through the array. The algorithm works by maintaining a candidate element m and a counter cnt:

1. Start with cnt = 0
2. For each element x in the array:
   • If cnt is 0, set the current element as the new candidate (m = x) and set cnt = 1
   • Otherwise, if the current element equals the candidate (m == x), increment the counter
   • If the current element is different from the candidate, decrement the counter

The key insight is that the majority element will "survive" this voting process because it appears more than half the time. Every time a non-majority element decrements the counter, there are still enough majority elements left to maintain dominance.

Intuition

Think of this problem as a voting competition where different candidates (array elements) are trying to win. The key insight is that if one candidate appears more than half the time, they have an absolute majority - they can't be defeated even if all other candidates team up against them.

Imagine pairing up elements in the array. When we see two different elements, we can "cancel them out" - like opposing votes nullifying each other. Since the majority element appears more than n/2 times, even after all possible cancellations with different elements, the majority element will still have leftover occurrences.

This leads us to a clever counting strategy: we maintain a candidate and a counter. The counter represents how many "uncanceled" votes our current candidate has. When we encounter the same element as our candidate, it strengthens their position (increment counter). When we encounter a different element, it challenges the candidate (decrement counter).

When the counter reaches zero, it means all previous votes have been canceled out, so we start fresh with a new candidate. The beautiful part is that the true majority element will always survive this process because:

1. If the majority element is currently the candidate, there aren't enough other elements to completely cancel it out
2. If a non-majority element becomes the candidate temporarily, it will eventually be overthrown because it doesn't have enough support

By the end of the array, the surviving candidate must be the majority element. This works because we're guaranteed a majority exists - if we remove pairs of different elements from the array, the majority element will always remain due to its dominance in numbers.

This approach transforms what could be a counting problem requiring extra space (like using a hash map) into an elegant single-pass solution with O(1) space complexity.

Solution Approach

The implementation uses the Boyer-Moore Voting Algorithm, which processes the array in a single pass with constant space complexity.

Let's walk through the algorithm step by step:

Initialization:

• Set cnt = 0 (counter for tracking the current candidate's strength)
• Set m = 0 (variable to store the current candidate element)

Main Loop: For each element x in the array nums:

1. Check if counter is zero (if cnt == 0):

   • This means we either just started or all previous votes have been canceled
   • Set the current element as the new candidate: m = x
   • Initialize the counter to 1: cnt = 1

2. Otherwise, update the counter based on the current element:

   • If m == x (current element matches our candidate):
     • Increment the counter: cnt = cnt + 1
     • This strengthens the candidate's position
   • If m != x (current element is different from our candidate):
     • Decrement the counter: cnt = cnt - 1
     • This represents a cancellation between different elements

Return the result: After processing all elements, return m as the majority element.

Why this works:

• The majority element appears more than n/2 times
• Even if every non-majority element tries to cancel out the majority element (by decrementing its counter), there aren't enough of them to completely eliminate it
• The final candidate m that survives must be the majority element

Time and Space Complexity:

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(1) - only using two variables (cnt and m)

The elegance of this algorithm lies in its ability to find the majority element without explicitly counting occurrences or using additional data structures like hash maps.

Example Walkthrough

Let's walk through the Boyer-Moore Voting Algorithm with a concrete example.

Example array: nums = [2, 2, 1, 1, 1, 2, 2]

In this array of size 7, the majority element must appear more than 3 times. Let's trace through the algorithm:

Initial state:

• cnt = 0
• m = 0 (placeholder, will be set when cnt is 0)

Step-by-step execution:

Final result: m = 2

Let's verify: Element 2 appears 4 times in the array (positions 0, 1, 5, 6), which is more than ⌊7/2⌋ = 3, confirming it's the majority element.

Key observations from this walkthrough:

1. When we encounter matching elements (steps 1-2), the counter increases, strengthening the candidate
2. When different elements appear (steps 3-4), they "cancel out" with the candidate
3. When the counter reaches 0 (steps 5, 7), we reset with a new candidate
4. The true majority element (2) eventually emerges as the final candidate despite temporarily losing the position to element 1

This demonstrates how the majority element survives the voting process due to its numerical dominance in the array.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array exactly once, performing constant-time operations (comparisons and arithmetic operations) for each element.

The space complexity is O(1). The algorithm only uses two variables (cnt and m) to track the candidate element and its count, regardless of the input size. No additional data structures are created that scale with the input.

Common Pitfalls

1. Attempting to Verify the Result When Not Required

A common mistake is adding unnecessary verification code after the Boyer-Moore algorithm to confirm that the candidate is indeed the majority element:

# Unnecessary verification
candidate = boyer_moore_result
count = sum(1 for num in nums if num == candidate)
if count > len(nums) // 2:
    return candidate
else:
    return -1  # This will never happen given the problem constraints

Why it's a pitfall: The problem explicitly guarantees that a majority element exists, so verification adds unnecessary O(n) time and makes the code more complex without any benefit.

2. Misunderstanding When Counter Resets

Some implementations incorrectly reset the counter only when it becomes negative:

# Incorrect approach
if count < 0:  # Wrong condition!
    candidate = num
    count = 1

The correct approach: The counter should reset when it reaches exactly 0, not when it becomes negative:

if count == 0:
    candidate = num
    count = 1

3. Incorrect Counter Update Logic

A subtle but critical mistake is updating the counter before checking if we need a new candidate:

# Incorrect order of operations
for num in nums:
    if candidate == num:
        count += 1
    else:
        count -= 1
  
    if count == 0:  # This check happens too late!
        candidate = num
        count = 1

Why it fails: When count becomes 0 after decrementing, we should immediately set the NEXT element as the candidate, not the current one that just caused the decrement.

Correct approach:

for num in nums:
    if count == 0:
        candidate = num
        count = 1
    elif candidate == num:
        count += 1
    else:
        count -= 1

4. Using the Algorithm When Majority Element May Not Exist

If you use Boyer-Moore in a scenario where a majority element might not exist (different from this problem), the algorithm will still return a candidate, but it won't necessarily be a majority element:

# Example where Boyer-Moore returns wrong result without verification
nums = [1, 2, 3]  # No majority element exists
# Boyer-Moore would return 3, but it's not a majority element

Solution: In problems where majority element existence isn't guaranteed, you must add a verification pass:

def majorityElement(nums):
    # First pass: Find candidate
    count = 0
    candidate = 0
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif candidate == num:
            count += 1
        else:
            count -= 1
  
    # Second pass: Verify (only needed if majority element might not exist)
    if nums.count(candidate) > len(nums) // 2:
        return candidate
    return None  # No majority element exists

5. Initializing Candidate with Invalid Value

While initializing candidate = 0 works fine (since it gets overwritten immediately), some might try to use special values that could cause issues:

# Potentially problematic if nums could contain None
candidate = None

Better practice: Since the candidate is always set in the first iteration when count == 0, the initial value doesn't matter, but using a simple integer like 0 avoids any potential type-related issues.