#169 Majority Element

frequently reported atAdobe Bloomberg Microsoft Amazon Google TCS

the problem

In plain words

Return the majority element: the value that appears more than ⌊n / 2⌋ times. The input always has one. Follow-up: can you do it in O(n) time with O(1) extra memory?

in nums = [3,2,3]

out 3

in nums = [2,2,1,1,1,2,2]

out 2

2 appears 4 times out of 7.

1 ≤ n ≤ 5·10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
A majority element always exists
Follow-up: O(n) time, O(1) space

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBoyer–Moore majority vote Frequency counting

Pair each copy of the majority with a different value and throw both away. The majority has more copies than all other values combined, so it is the only value that can survive the cancelling.

solutions

From brute force to optimal

For each element, count how often it appears with a second loop.

For each candidate: count its copies in a full scan.
Return it once the count passes n / 2.

timeO(n²)

A full scan per candidate: 2.5·10⁹ steps at n = 5·10⁴.

spaceO(1)

One counter.

javajava.util.*

1class Solution {2    public int majorityElement(int[] nums) {3        for (int candidate : nums) {4            int count = 0;5            for (int x : nums) if (x == candidate) count++; // a full scan per candidate6            if (count > nums.length / 2) return candidate;7        }8        return -1; // unreachable: a majority always exists9    }10}

A value filling more than half the slots must cover the middle slot once sorted.

Copy and sort.
Return copy[n / 2].

timeO(n log n)

The sort dominates.

spaceO(n)

The copy (sorting in place would mutate the caller's array).

javajava.util.*

1class Solution {2    public int majorityElement(int[] nums) {3        int[] copy = nums.clone();4        Arrays.sort(copy);5        return copy[copy.length / 2]; // more than half the slots: it must cover the middle one6    }7}

Count with merge; return the first value whose count passes n / 2.

count.merge(x, 1, Integer::sum) returns the new count.
If it exceeds n / 2, return x.

timeO(n)

One pass with O(1)-average map updates.

spaceO(n)

Up to about n / 2 distinct values are stored.

javajava.util.*

1class Solution {2    public int majorityElement(int[] nums) {3        Map<Integer, Integer> count = new HashMap<>();4        for (int x : nums) {5            if (count.merge(x, 1, Integer::sum) > nums.length / 2) return x; // merge returns the new count6        }7        return -1;8    }9}

Keep one candidate and a counter. A match adds a vote, a different value cancels one; at zero, the next value takes over.

candidate = 0, count = 0.
For each x: if count == 0, candidate = x.
count += (x == candidate) ? 1 : −1.
Return candidate.

timeO(n)

One pass, O(1) work per element.

spaceO(1)

Two variables.

javajava.util.*

1class Solution {2    public int majorityElement(int[] nums) {3        int candidate = 0, count = 0;4        for (int x : nums) {5            if (count == 0) candidate = x; // nobody is leading: x takes over6            count += (x == candidate) ? 1 : -1; // a vote for, or one that cancels a vote7        }8        return candidate; // the majority survives every cancellation9    }10}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public int majorityElement(int[] nums) {3        int candidate = 0, count = 0;4        for (int x : nums) {5            if (count == 0) candidate = x; // nobody is leading: x takes over6            count += (x == candidate) ? 1 : -1; // a vote for, or one that cancels a vote7        }8        return candidate; // the majority survives every cancellation9    }10}

in the room

How to say it in the interview

talk track

Start with the HashMap count: O(n) time, O(n) space.
Then: "two different values can cancel each other; the majority can never be fully cancelled" → Boyer–Moore, O(1) space.
Point out that the problem guarantees a majority. Without that guarantee, a second pass must count the candidate to confirm it.

traps

Without the guarantee, the survivor may not be a majority: [1,2,3] leaves 3. Verify with a second counting pass.
Writing count >= n / 2: for n = 6, a value with 3 copies is not a majority.

what they ask next

Follow-ups

Majority Element II (LC 229): every value appearing more than n / 3 times?

At most two such values exist. Keep two candidates and two counters, then verify both with a second pass.

Why does sorting work?

A value covering more than half of the slots must cover slot n / 2, wherever its run starts.

before you submit

Edge cases to test

n = 1 → that element.
The majority appears exactly ⌊n / 2⌋ + 1 times — the tightest case.
Negative and very large values: the vote only compares with ==, so no overflow is possible.

practise next