1. Base case
A single element is the majority of its own length-1 range.
if (left === right) return nums[left]Typorithm · medium
Majority Element
▷ Interactive algorithm labmajority-elementdivide-and-conquercombine-stepcandidatecount
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Majority Element
Divide & Conquer
Find each half's majority candidate; if they differ, count both across the range and keep the larger.
The majority element appears more than half the time, so it must be the majority of at least one half.
Recurse to get each half's candidate; if they match, it is the answer immediately.
When they disagree, a linear count over the range decides which candidate dominates.
Preparing algorithm lab…
01
Majority of the whole is majority of a half.
02
Agreeing halves settle it instantly.
03
Disagreeing halves need a count.
function majorityElement(nums, left = 0, right = nums.length - 1) {
if (left === right) return nums[left];
const mid = Math.floor((left + right) / 2);
const leftMajor = majorityElement(nums, left, mid);
const rightMajor = majorityElement(nums, mid + 1, right);
if (leftMajor === rightMajor) return leftMajor;
let leftCount = 0;
let rightCount = 0;
for (let i = left; i <= right; i += 1) {
if (nums[i] === leftMajor) leftCount += 1;
if (nums[i] === rightMajor) rightCount += 1;
}
return leftCount > rightCount ? leftMajor : rightMajor;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Conquer halves
Find the majority candidate of each half independently.
const rightMajor = majorityElement(nums, mid + 1, right)3. Halves agree
If both halves agree, that element is the overall majority.
if (leftMajor === rightMajor) return leftMajor4. Count in range
When halves disagree, count each candidate across the full range.
if (nums[i] === leftMajor) leftCount += 15. Pick the winner
The candidate that appears more often in this range wins.
return leftCount > rightCount ? leftMajor : rightMajorA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.