Find the Element Appearing More Than Half the Time

Given an array nums of size n, return the majority element — the value that appears MORE THAN ⌊n/2⌋ times. It's guaranteed that a majority element always exists. Counting each candidate's occurrences by rescanning the array works, but it repeats a lot of counting across candidates. The Boyer-Moore Voting Algorithm answers this in one O(n) pass with O(1) space, by treating the scan as an election that the majority element can never lose.

Test Case 1:

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

Output:2

Explanation:2 appears 4 times out of 7 — more than half.

Test Case 2:

Input:nums = [3, 2, 3]

Output:3

Explanation:3 appears twice out of 3 — more than half.

Test Case 3:

Input:nums = [1]

Output:1

Explanation:A single element is trivially its own majority.

Constraints

◆1 ≤ nums.length ≤ 5 × 10⁴
◆-2³¹ ≤ nums[i] ≤ 2³¹ - 1
◆It is guaranteed nums always has a majority element.

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 3-9 integers, -10 to 10

1	class Solution {
2	public int majorityElement(int[] nums) {
3	int candidate = nums[0], count = 0;
4	for (int num : nums) {
5	if (count == 0) {
6	candidate = num;
7	}
8	count += (num == candidate) ? 1 : -1;
9	}
10	return candidate;
11	}
12	}
13

2

1

2

0

1

2

3

4

5

6

Variables

candidate2

count0

INITIALIZE

Start with candidate = nums[0] = 2 and count = 0.

Step 1 / 12

Approach & Solutions

Brute Force

Brute

For each candidate index, scan the entire array counting how many times that value occurs. As soon as a count exceeds half the array's length, that value is the answer. Correct, but every candidate re-scans the whole array from scratch.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int majorityElement(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == nums[i]) count++;
            }
            if (count > nums.length / 2) return nums[i];
        }
        return -1;
    }
}

Optimal — Boyer-Moore Voting Algorithm

Optimal

Walk the array once, keeping a candidate and a vote count. Every element that matches the candidate casts a vote for it; every element that doesn't casts a vote against it. If the count ever drops to 0, the current candidate has been fully cancelled out — adopt whatever element comes next as the new candidate. Since the true majority element appears more than half the time, the votes against it (cast by every other value combined) can never fully cancel it out — whichever candidate survives to the end must be it.

TimeO(n)