What pattern does Majority Element use?

The Pattern: Greedy Algorithms (Boyer-Moore Voting) The Heuristic: When a majority element exists, pairing off different elements and canceling them leads to the majority element surviving; tracking a candidate and count with increments and decrements efficiently finds it in one pass with constant space.

Majority Element - LeetCode Solution & Explanation

Q: What is the time complexity of Majority Element?

O(n). The algorithm makes a single pass through the array, performing constant time operations per element.

Problem

Given an integer array nums of size n, return the majority element, which is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

1 ≤ nums.length ≤ 5 * 10⁴
−10⁹ ≤ nums[i] ≤ 10⁹
The majority element always exists in the array

Example

Input: nums = [2,2,1,1,1,2,2]

Output: 2

A brute-force approach would count the frequency of each element and return the one with count greater than n/2. For the input, 2 appears 4 times and 1 appears 3 times. The algorithm uses a voting mechanism to track a candidate and its count. Initially, candidate is None and count is 0. Iterating through nums: at first 2, count is 0 so candidate becomes 2 and count increments to 1. Next 2 matches candidate, count increments to 2. Next 1 does not match candidate, count decrements to 1. Next 1 again does not match candidate, count decrements to 0. When count reaches 0, candidate updates to next element 1, count increments to 1. Next 2 does not match candidate, count decrements to 0. Next 2 updates candidate to 2, count increments to 1. Next 2 matches candidate, count increments to 2. At the end, candidate is 2, which is the majority element.

Approach

Straightforward Solution

A brute-force approach counts the frequency of each element using a hash map and returns the element with count > n/2. This requires O(n) time and O(n) space, which is acceptable but not optimal in space.

Core Observation

The majority element appears more than half the time, so it cannot be completely canceled out by other elements. This guarantees that a voting mechanism that increments count for the candidate and decrements for others will end with the majority element as the candidate.

Path to Optimal

The key insight is that since the majority element appears more than half the time, it can be found by pairing off different elements and canceling them out. The Boyer-Moore Voting Algorithm exploits this by maintaining a candidate and a count. When count drops to zero, the candidate is replaced. This process guarantees the candidate at the end is the majority element, using only O(1) space and O(n) time.

Optimal Approach

Iterate through the array, maintaining a candidate and a count. When count is zero, set the candidate to the current element. If the current element equals the candidate, increment count; otherwise, decrement count. After one pass, return the candidate. This works because the majority element cannot be fully canceled out by other elements.

Time

O(n)

The algorithm makes a single pass through the array, performing constant time operations per element.

Space

O(1)

Only two variables (candidate and count) are maintained regardless of input size, resulting in constant auxiliary space.

Solution

1class Solution:
2    def majorityElement(self, nums: List[int]) -> int:
3
4        candidate = None
5        count = 0
6
7        for n in nums:
8
9            if count == 0:
10                candidate = n
11
12            if n == candidate:
13                count += 1
14            else:
15                count -= 1
16
17        return candidate

Step-by-Step Solution

1

Initialize Candidate and Count to Track Majority Element

4candidate = None
5count = 0

Objective

To set up variables that will hold the current candidate for majority and its vote count.

Key Insight

Starting with no candidate and zero count allows the algorithm to assign the first element as candidate and begin counting votes. This initialization is critical because it sets the baseline for the voting process that follows.

Interview Quick-Check

Core Logic

Candidate and count variables maintain the current majority candidate and its relative vote count.

State & Boundaries

Count starts at zero to indicate no current candidate, triggering candidate assignment on first iteration.

2

Iterate Through Array to Update Candidate and Vote Count

7for n in nums:
  if count == 0:
      candidate = n
  if n == candidate:
      count += 1
  else:
      count -= 1

Objective

To process each element, updating the candidate and count according to the Boyer-Moore voting rules.

Key Insight

When count is zero, the current element becomes the new candidate because previous candidates have been canceled out. If the current element matches the candidate, increment count to reinforce its majority status. Otherwise, decrement count to represent cancellation by a different element. This greedy approach ensures the majority element survives all cancellations.

Interview Quick-Check

Core Logic

The algorithm pairs off different elements by incrementing count for matches and decrementing for mismatches, ensuring the majority element remains as candidate.

State & Boundaries

Resetting candidate when count reaches zero ensures the algorithm adapts to new potential majority elements.

Common Pitfalls & Bugs

Failing to reset candidate when count is zero or incorrectly updating count leads to wrong results.

3

Return the Final Candidate as the Majority Element

17	`return candidate`

Objective

To output the candidate that survived all cancellations as the majority element.

Key Insight

Because the majority element appears more than half the time, it cannot be fully canceled out, so the candidate at the end of iteration is guaranteed to be the majority element. Returning it completes the algorithm efficiently.

Interview Quick-Check

Core Logic

The final candidate is the majority element due to the guaranteed survival through the voting process.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

if count == 0:

Check if count has dropped to zero to reset candidate.

Resetting the candidate when count reaches zero is the critical step that allows the algorithm to discard invalid candidates and focus on the true majority element.

Line 15 Critical

count -= 1

Decrement count when current element differs from candidate.

This decrement is the core of the Boyer-Moore algorithm's cancellation logic, enabling the majority element to prevail by offsetting votes from minority elements.

Line 12 Core

if n == candidate:

Check if the current element matches the candidate.

Matching the candidate means reinforcing its vote count, which is essential to track the majority element's dominance.

Line 13 Core

count += 1

Increment count when current element matches candidate.

Incrementing count represents gaining a vote for the candidate, increasing confidence that it is the majority element.

Line 17 Core

return candidate

Return the candidate after processing all elements.

Returning the candidate completes the algorithm, as it is guaranteed to be the majority element due to the voting mechanism.

Line 4 Core

candidate = None

Initialize candidate to None before iteration.

Starting with no candidate allows the algorithm to assign the first element encountered as the initial candidate, enabling the voting process to begin correctly.

Line 5 Core

count = 0

Initialize count to zero to indicate no votes yet.

Count zero signals that there is currently no candidate being tracked, so the next element will become the candidate, ensuring the algorithm adapts dynamically.

Line 10 Core

candidate = n

Assign the current element as the new candidate.

This assignment updates the candidate to the current element, which may be the majority element or a potential candidate to be confirmed by subsequent votes.

Line 14 Core

else:

Handle the case when current element does not match candidate.

This else branch represents encountering a different element, which cancels out one vote from the candidate, reflecting the competition among elements.

Line 7 Standard

for n in nums:

Begin iterating through each element in the input array.

Processing each element is necessary to apply the voting logic and identify the majority element in a single pass.

Test Your Understanding

Why does the Boyer-Moore Voting Algorithm guarantee that the candidate at the end is the majority element?

Because the majority element appears more than half the time, it cannot be completely canceled out by other elements during the increment/decrement process, ensuring it remains as the candidate after all pairings.

Don't just read it. Drill it.

Reconstruct Majority Element from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Majority Element drill

or drill a free problem

1	`class Solution:`
2	`def majorityElement(self, nums: List[int]) -> int:`
3
4	`candidate = None`
5	`count = 0`
6
7	`for n in nums:`
8
9	`if count == 0:`
10	`candidate = n`
11
12	`if n == candidate:`
13	`count += 1`
14	`else:`
15	`count -= 1`
16
17	`return candidate`

7	`for n in nums:`
9	`if count == 0:`
10	`candidate = n`
12	`if n == candidate:`
13	`count += 1`
14	`else:`
15	`count -= 1`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Candidate and Count to Track Majority Element

Iterate Through Array to Update Candidate and Vote Count

Return the Final Candidate as the Majority Element

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.