Majority Element
An easy Arrays problem included in Apna College, Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Arrays
- Sheets
- 3
- Core for
- 25 roles
- Platform
- LeetCode
The problem
Given an array of size n, identify the majority element that occurs strictly more than n / 2 times.
Example 1
- Input
- nums = [3,2,3]
- Output
- 3
- Why
- The number 3 appears 2 times, which exceeds 3 / 2 = 1.5 times.
Example 2
- Input
- nums = [2,2,1,1,1,2,2]
- Output
- 2
- Why
- The number 2 appears 4 times, strictly greater than 7 / 2 = 3.5 times.
Example 3
- Input
- nums = [1]
- Output
- 1
- Why
- The single element appears once, exceeding 1 / 2 = 0.5.
Constraints
- 1 <= nums.length <= 5*10^4
- -10^9 <= nums[i] <= 10^9
How to think about it
Updated 2026-09-09An element holding more than half the total votes can survive being paired off and canceled against every other competing element combined. Discarding any two differing elements leaves the true majority element invariant, which means one candidate and one tally variable are sufficient to isolate the winner without saving past values.
Approaches, worst first
Frequency hash map
time O(n) · space O(n)
Record the frequency count of each number in a hash table. Scan through the counts until encountering a value strictly exceeding floor(n / 2). Robust and requires no ordering assumptions, but incurs linear extra memory overhead.
Sorting and middle index access
time O(n log n) · space O(1)
Sort the array ascending. Because the majority element covers strictly more than half the length, its contiguous span must bridge the middle index n / 2 regardless of where it starts, making nums[n / 2] the definitive answer.
Boyer-Moore votingWrite this one
time O(n) · space O(1)
Maintain candidate and count initialized to 0. For each element, if count is 0, assign candidate to the current value. Increment count if the number equals candidate; otherwise decrement count. The surviving candidate is the majority element.
Where people lose marks · 3
- Applying Boyer-Moore voting without a second verification pass when the problem statement does not guarantee the existence of a majority element.
- Initializing the count to 1 with an unassigned or zero candidate, distorting votes if the first element is non-zero.
- Dividing n / 2 with integer truncation and checking `>= n / 2` instead of `> n / 2`, which misidentifies ties in even-length inputs.
Full solution
Boyer-Moore voting: pairing off differing elements cannot eliminate a value that holds more than half the votes, so one candidate and one counter find it in O(n) time and O(1) space. No verification pass is needed because the statement guarantees the majority element exists.
Python
def majority_element(nums: list[int]) -> int:
candidate = 0
count = 0
for num in nums:
if count == 0:
candidate = num # every prior vote has been cancelled; restart here
count += 1 if num == candidate else -1
return candidate
JavaScript
function majorityElement(nums) {
let candidate = 0;
let count = 0;
for (const num of nums) {
if (count === 0) candidate = num; // every prior vote has been cancelled; restart here
count += num === candidate ? 1 : -1;
}
return candidate;
}
The theory behind it
Arrays — the ground this problem stands on. All Arrays problems
What Arrays is
An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.
When to reach for it
Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.
How the pattern works
Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.
What each operation costs
| Operation | Time |
|---|---|
| look up element by index | O(1) |
| insert or delete at the start | O(n) |
| search an unsorted collection for a value | O(n) |
What usually goes wrong with Arrays
- Reading past the final index by checking index less than or equal to length instead of strictly less than length, triggering index out of bounds exceptions.
- Modifying length or removing elements during a forward iteration loop, which causes remaining items to shift left and skip validation on the next neighbor.
- Assuming dynamic resizing is costless inside nested loops, causing repeated memory reallocation copies when appending unknown quantities of items.
Which roles need this problem
Arrays is a core topic for these 25 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 3 more roles, including Database Engineer, Bioinformatics Engineer, Networking Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Arrays problems
Problem set and role mapping as of .