Majority Element Solutions & Complexity

1. Define the problem

Majority Element

Given an array nums of size n, return the majority element . You may assume the majority element always exists in the array. Use Boyer-Moore voting : keep a candidate and a count, incrementing the count on a match and decrementing on a mismatch — when the count hits zero, switch to a new candidate.

Constraints

n == nums.length
1 ≤ n ≤ 5 × 10⁴
-10⁹ ≤ nums_i ≤ 10⁹
The majority element always exists

Example

Inputnums = [2, 2, 1, 1, 1, 2, 2]

Output2

Explanation 2 appears four times out of seven elements, more than half, so it is the majority element.

2. Know the words first

In plain terms

Majority element: The value that appears more than n/2 times in an array of length n — strictly more than half of all the elements.
Boyer-Moore voting: A trick where matching values "vote" for a candidate and mismatches "cancel out" a vote, so the true majority value always survives to the end.

3. Visualize the solution

Vote for a candidate, cancel out on mismatches

Statusinit

i=0 (value 2). count=0, so candidate becomes 2, count=1.

What happens in this step

i = 0 (value 2), count = 0
count is 0, so candidate = 2

count becomes 1.

Step 1 of 5

Steps to visualize

Start with no candidate and a count of 0.
For each value: if count is 0, make this value the new candidate.
If the value matches the candidate, increment count; otherwise decrement count.
After scanning every value, the surviving candidate is the majority element.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Vote for a candidate, cancel out on mismatches

Statusinit

i=0 (value 2). count=0, so candidate becomes 2, count=1.

What happens in this step

i = 0 (value 2), count = 0
count is 0, so candidate = 2

count becomes 1.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function majorityElement(nums) {
  let candidate = null;
  let count = 0;

  for (const value of nums) {
    if (count === 0) {
      candidate = value;
    }

    count += value === candidate ? 1 : -1;
  }

  return candidate;
}

Time: O(n)
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [2, 2, 1, 1, 1, 2, 2]`	`2`	example from the docstring
`nums = [7]`	`7`	smallest valid input, a single element
`nums = [3, 3, 4]`	`3`	majority element appears at the start rather than scattered
`nums = [5, 5, 5, 5]`	`5`	every element is identical
`nums = [-1, -1, -1, 2, 2]`	`-1`	negative values as the majority element
`nums = [1, 1, 2, 1, 2]`	`1`	majority just barely exceeds half the array

Majority Element