Imagine you are handed an array of integers, such as [3, 2, 3], with a length $n=3$. Your goal is to find the majority element—the value that appears strictly more than $\frac{n}{2}$ times. In our first case, that number is 3. Later, we will face a longer sequence: [2, 2, 1, 1, 1, 2, 2], where the majority element is 2. How would you normally solve this?

If you reach for a hash map to count every occurrence, you instantly violate our constraint of $O(1)$ extra space. For a massive dataset, allocating a frequency table for every unique element consumes memory proportional to the number of distinct items. When $n$ scales into the millions, building a full frequency dictionary becomes a severe performance bottleneck.

What if we sort the array to find the middle element? Sorting solves the space problem in-place, but it forces a time complexity of $O(n\log n)$. Can we do better? Can we identify the dominant value in a single linear pass without saving every distinct number in memory?

To see why this is tricky, look at how the numbers clash in [2, 2, 1, 1, 1, 2, 2]. The minority elements try to drown out the majority, yet the majority still holds a strict numerical advantage. We need a mechanism that lets elements cancel each other out dynamically, preserving only the survivor.

When scanning through our locked example nums = [3, 2, 3], we want to avoid building a heavy frequency map of every element. Instead, imagine a political election or a tug-of-war where every element with a different value cancels out an opposing vote. We maintain a single candidate and a count representing its current surplus of supporters. If the count drops to zero, the current candidate has been entirely depleted, and we simply adopt the next incoming element as our new candidate with a count of 1.

Let us trace the first two items of our primary array [3, 2, 3] through this mental model. We start with candidate = None and count = 0. When we see 3, the count is zero, so candidate = 3 and count = 1. Next, we inspect 2. Since 2 does not equal our candidate 3, we decrement count to 0. The candidate 3 and the challenger 2 have mutually canceled each other out.

This cancellation mechanic guarantees that if a true majority element exists—appearing strictly more than $\frac{n}{2}$ times—it possesses more votes than all other elements combined. Even if the non-majority elements gang up on it, the sheer density of the majority guarantees it will outlast the skirmish and hold the candidate seat at the end of the array.

Let $M$ be the majority element in an array of length $n$, appearing $k$ times where $k>\frac{n}{2}$. The remaining elements sum to $n-k$ appearances. Because $k>n-k$, the difference $2k-n$ is strictly greater than zero. This positive net surplus ensures that no matter how the elements are interleaved, $M$ cannot be permanently defeated.

Let us run the tug-of-war model explicitly on our two working examples: nums = [3, 2, 3] and nums = [2, 2, 1, 1, 1, 2, 2]. We maintain two variables during the pass: candidate (initialized to None or an arbitrary value) and count (initialized to 0). Every time count hits 0, we adopt the current element as our new candidate. Then, if the current element matches the candidate, we increment count; otherwise, we decrement it.

- Given: nums = [3, 2, 3] with $n=3$. The majority element must appear strictly more than $3/2=1.5$ times (i.e., at least 2 times).
- Step 1: Start with candidate = None, count = 0.
- Step 2: Inspect x = 3. Since count == 0, set candidate = 3. Now x == candidate, so count becomes 1. State: candidate = 3, count = 1.
- Step 3: Inspect x = 2. Since 2 != 3, decrement count to 0. State: candidate = 3, count = 0.
- Step 4: Inspect x = 3. Since count == 0, reset candidate = 3. Now x == candidate, so increment count to 1. State: candidate = 3, count = 1.
- Result: Loop ends. The surviving candidate is 3, which correctly matches our expected result.

- Given: nums = [2, 2, 1, 1, 1, 2, 2] with $n=7$. The majority threshold is $>3.5$ times (at least 4 times).

- Index 0 (x = 2): count == 0, so candidate = 2, count = 1.
- Index 1 (x = 2): 2 == candidate, so count increments to 2. State: candidate = 2, count = 2.
- Index 2 (x = 1): 1 != candidate, so count decrements to 1. State: candidate = 2, count = 1.
- Index 3 (x = 1): 1 != candidate, so count decrements to 0. State: candidate = 2, count = 0.
- Index 4 (x = 1): count == 0, so candidate = 1, count = 1.
- Index 5 (x = 2): 2 != candidate, so count decrements to 0. State: candidate = 1, count = 0.
- Index 6 (x = 2): count == 0, so candidate = 2, count = 1.
- Result: The final surviving candidate is 2, which appears 4 times out of 7 and satisfies our condition.

Try this: Trace the execution of Boyer-Moore on nums = [1, 1, 2, 1, 2, 2, 2] with n=7. What is the candidate and count after processing the fourth element (value 1 at index 3)?

To solidify the tug-of-war model, trace the loop iteration by iteration:
- Start with cand = None, count = 0.
- For x = 1, count becomes 1, cand = 1.
- For x = 1, count becomes 2, cand = 1.
- For x = 2, count drops to 1, cand remains 1.
- Continue for the remaining elements 1 and 2 to see who ultimately holds the field.

Write out or mentally determine the exact (cand, count) pair immediately after processing the fourth element (x = 1) in nums = [1, 1, 2, 1, 2], and state what the final returned candidate will be.

Try this: nums = [1, 1, 2, 1, 2]

Trace: initial (None, 0)

x = 1 -> (1, 1)

x = 1 -> (1, 2)

x = 2 -> (1, 1)

x = 1 -> ?

x = 2 -> ?

Now that you have traced the Boyer-Moore cancellation loop on nums = [3, 2, 3] and [2, 2, 1, 1, 1, 2, 2], it is time to transfer this pattern to a related variant. The core insight of Boyer-Moore is not just about finding a majority element; it is about maintaining a stabilizing candidate against a background of noise through pairwise reduction. Consider a modified problem: what if we need to find all elements that appear more than $n/3$ times in an array of size $n$, still using $O(1)$ extra space beyond our fixed output size?

To solve this generalized version, our single-candidate tug-of-war model naturally expands into a two-candidate duel. Instead of tracking one cand and count, we now maintain up to two candidates (cand1, cand2) and their respective counts (count1, count2). As you iterate through the stream, each incoming element is compared against both active candidates. If it matches one, its count increments. If neither matches and an empty slot is available, it becomes a new candidate with a count of 1. If both slots are occupied and it matches neither, both counts decrement by 1, effectively canceling out three distinct elements at once.

After passing through the entire array once to find potential survivors, a mandatory second verification pass is required to count the actual frequencies of cand1 and cand2. This mirrors the verification step we discussed for standard majority elements when the existence of a majority is not guaranteed. By adapting the cancellation invariant from one candidate to $k-1$ candidates, you can solve the $n/k$ threshold problem with optimal linear time and constant auxiliary space.

def majority_element_n_over_3(nums):
    # TODO: Implement the two-candidate Boyer-Moore variant
    pass