Majority Element

Problem in Plain English

Given an array of size n where one element appears more than n divided by 2 times, return that majority element. The input guarantees such an element always exists.

Problem Statement

Given an integer array nums of length n, return the value that occurs strictly more than half the time. Such a majority element is guaranteed to exist.

A majority needs at least floor(n / 2) + 1 occurrences; being the most frequent value alone is insufficient.

Follow-up: find it in $O(n)$ time with $O(1)$ extra space.

Constraints

n == nums.length
1 <= n <= 5 * 10^4
-10^9 <= nums[i] <= 10^9
A majority element always exists.

Examples

Example 1

Input: nums = [3, 2, 3]
Output: 3

3 appears twice, which is more than 3 / 2 = 1.5, so 3 is the majority element.

Example 2

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

2 appears four times, which is more than 7 / 2 = 3.5, so 2 is the majority element.

Example 3

Input: nums = [-1]
Output: -1

The only value occurs once, more than 1 / 2. A negative majority is a valid answer, so -1 must not be treated as a missing-answer marker.

Intuition

Imagine removing two different values together until no such pair remains. Each pair consumes at most one occurrence of the majority, and there are fewer other values than majority occurrences, so some majority occurrences must survive. In [3, 2, 3], cancelling the first 3 with 2 leaves 3. Boyer-Moore voting simulates these removals with a candidate value and a count of its unmatched occurrences; that count is not the candidate's total frequency.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Treat each position as a candidate and count its occurrences with a full rescan of the array. The first candidate whose count passes half the length is the answer, at the price of a scan per candidate.

Step-by-Step Logic

Set threshold = floor(n / 2). For Example 1, [3, 2, 3] has threshold = 1.
For each possible candidate nums[i], start count = 0 and scan every value in the array.
Increment count for equal values. Candidate 3 sees counts 1, 1, and 2 on Example 1.
After the full scan, return the candidate if count > threshold. Here 2 > 1, so return 3; otherwise try the next candidate.

Why It Works

After scanning any prefix, count equals the number of occurrences of nums[i] in that prefix: it starts at zero and increases exactly on a match. After the whole array, a count above floor(n / 2) proves that candidate is the majority. Every distinct value is eventually considered unless an answer is found first, so the guaranteed majority cannot be missed. Two different values cannot both exceed half the length, making the returned answer unique.

Dry Run

Brute Force: variable states at each step
Event	i	Candidate	Value read	Count before	Count after	Threshold	Decision
Start candidate	`0`	`3`	none	none	`0`	`1`	start full scan
Read index 0	`0`	`3`	`3`	`0`	`1`	`1`	equal, increment
Read index 1	`0`	`3`	`2`	`1`	`1`	`1`	different, leave count
Read index 2	`0`	`3`	`3`	`1`	`2`	`1`	equal, increment
End full scan	`0`	`3`	none	`2`	`2`	`1`	`2 > 1`, return `3`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

Worst case, a majority is first encountered only after about n/2 minority positions. Each unsuccessful candidate still scans all n values, giving quadratic time. Example 1 returns after one scan, but does not determine the worst-case bound. Only the threshold, candidate position, current value, and count are stored, so extra space is constant; the input is not modified.

Code

Solution.java

1class Solution {2    public int majorityElement(int[] nums) {3        int threshold = nums.length / 2;4        for (int i = 0; i < nums.length; i++) {5            int count = 0;6            for (int num : nums) {7                if (num == nums[i]) {8                    count++;9                }10            }11            if (count > threshold) {12                return nums[i];13            }14        }15        // Unreachable: the input guarantees a majority exists.16        throw new IllegalStateException("Majority guarantee violated");17    }18}

Hints

Hint 1

Counting every candidate separately works but rescans the array each time; consider what that costs at 5 * 10^4 elements.

Hint 2

A sorted array would place the majority at the middle index, which hints that the majority outnumbers the rest combined.

Hint 3

Keep one candidate plus a counter: adopt a new candidate at zero, then add or subtract one vote per value.

Edge Cases

Single value: [-1] returns -1; zero and negative candidates are ordinary values, not special markers.
All equal: [7, 7, 7, 7] returns 7, and the voting count increases on every element.
Minimum even-length majority: [1, 2, 2, 2] returns 2; two copies would only tie half the length.
Several resets: [1, 2, 3, 3, 3] cancels 1 with 2, then adopts the later majority 3.
Extreme integers: [-1000000000, 1000000000, -1000000000] returns -1000000000; the algorithm compares values without subtracting them.
Without the guarantee: [1, 2, 3] leaves a candidate but has no majority. That variant requires a frequency verification pass; empty arrays are outside this problem's constraints.

Common Mistakes and Interview Tips

Using count >= floor(n / 2) in brute force admits a tie; use a strict greater-than comparison.
Treating the voting count as a frequency: Example 1 finishes at 1 although the majority 3 occurs twice.
Counting a mismatching value again as a new vote immediately after it brings count to zero. It already cancelled a vote; the next value starts the fresh candidacy.
Adopting a candidate but failing to count the current element as its first vote. Set the candidate before the equality-based update.
Interview tip: state the majority guarantee before omitting verification, and explain the cancellation invariant rather than assuming the last candidate is always valid.

Key Takeaway

When one value is guaranteed to outnumber all others combined, pairwise cancellation finds it in linear time with constant space.