Majority Element I
đź’» Try it yourself first. Write your solution in Java, C++, Python or JavaScript and run it against hidden tests, right here.Revision notes
Majority Element I (LeetCode 169)
Short revision notes for the LearnWithKiriti episode, starring Kodee.
Problem
An array shelf of size numbers. Return the value that appears more than size / 2 times (on more than half the shelf). LeetCode promises it exists.
shelf = [3, 7, 7, 5, 7]
answer = 7
Why 7? It is on 3 of the 5 books. Half of 5 is 2.5, and 3 is more than that. “More than half” is not the same as “most common”.
Blank mind in the interview? Ask three small questions
- What would I do by hand, on a tiny example?
- What is the dumbest thing that works? (brute force)
- What does it cost? Then improve it one step at a time.
Never jump straight to the optimal answer. It looks memorised. Start with the brute force, state its cost, then improve it.
The approaches
| Folder | Idea | Use it when |
|---|---|---|
| Brute | For each volume, count its copies on the whole shelf | Warm-up only |
| Better-HashMap | One walk, copiesOf[volume]++, return when a count passes half |
Memory is no problem, you want it simple |
| Optimal/1-BitCounting | For each of the 32 bits, count the ones; a bit with more than half the votes belongs to the answer | O(1) space, integers only |
| Optimal/2-BoyerMooreVoting | Pair off two DIFFERENT values and throw both away: keep only candidate and votes (+ majorityOrNone, the verify pass) |
Any type, a stream, or no majority promised |
Which one should I pick?
Is a majority promised?
├── Yes ── Memory is no problem, want it simple? ── Hash map counting
│ Numbers only, want O(1) space? ───────── Bit counting
│ Titles, any comparable type, a stream? ─ Boyer-Moore Voting
└── No ─── Boyer-Moore, then verify (majorityOrNone)
Other ways exist: sort and take the middle, pick at random, or divide and conquer. None beats these two optimals in an interview.
Complexity (n = size of shelf)
| Approach | Time | Extra space | Passes | Works on |
|---|---|---|---|---|
| Brute (count every volume) | O(n x n) | O(1) | n scans | any type that compares |
| Hash map counting | O(n) | O(n), one entry per different volume | 1 | any type that hashes |
| Bit counting | O(32 x n) = O(n) | O(1) | 32 | integers only |
| Boyer-Moore Voting | O(n) | O(1) | 1 (2 with verify) | any type that compares for equality |
Space, honestly:
- Hash map: the map holds one entry per DIFFERENT volume. That is up to about n / 2 entries, so O(n), not O(1).
- Bit counting is O(1) because a number has a fixed 32 bits. It only works on integers. Bit 31 is the sign bit:
- Java
intand JavaScript|are 32-bit signed, so turning bit 31 on gives the right negative number. - C++ builds
answeras anunsigned int(shifting a 1 into the sign bit of a signedintis not safe), then casts back toint. - Python ints have no fixed size, so
answercan reach2 ** 31or more. Subtract2 ** 32to get the negative number back.
- Java
- Boyer-Moore: two variables, and it never changes the shelf.
No majority promised? The verify pass
If a majority exists, Boyer-Moore’s candidate is it. If none exists, the candidate is just a guess. Example [2, 2, 1, 1, 3, 1]: no value is on more than 3 books, yet the walk ends with candidate 3. So walk once more, count the candidate, and compare with half (majorityOrNone in the Boyer-Moore files). Still O(n) time, O(1) space.
Our code returns -1 for “no majority” to keep it short. But -1 could be a real volume: in real code return null (Java Integer), None (Python), null (JavaScript), or std::optional / a flag in C++.
Bridge: LeetCode 229, Majority Element II (more than n / 3)
At most TWO values can be on more than a third of the shelf (three of them would need more than the whole shelf). So keep two candidates, each with its own votes. A book that matches neither cancels one vote from EACH (a triple leaves together). Always verify both at the end.
The general rule: more than n / k means at most k - 1 candidates. Full code in a later episode.
Folder layout
Every approach folder has pseudocode.md and the same code in Java/, C++/, Python/ and JS/. The code is exactly what is on screen. Every file runs as it is and prints Majority: 7.
javac MajorityMoore.java && java MajorityMoore
g++ majority_moore.cpp -o majority_moore && ./majority_moore
python majority_moore.py
node majorityMoore.js
Submitting on LeetCode
LeetCode 169 names the method majorityElement(nums) (Python: majorityElement(self, nums) inside class Solution). Copy the function body and rename shelf to nums. The final return -1 is never reached, because LeetCode promises a majority.
Rebuild it (pause, say it out loud, then check)
- The key observation is… pairing off two different books never removes the majority.
- When the value differs I… take one vote away, because that pair leaves together.
- It costs… O(n) time, O(1) space.
Next up: Leaders in an Array (the idea behind LeetCode 1299).
Brute
Brute Force: count every volume
Idea
Take each volume. Count its copies on the whole shelf. If the count is more than half the shelf, that volume is the answer.
Pseudocode
majorityElement(shelf):
size = number of books in shelf
for volume in shelf:
copies = 0
for book in shelf:
if book == volume:
copies = copies + 1
if copies > size / 2:
return volume
Dry run: shelf = [3, 7, 7, 5, 7], size = 5, so we need copies above 2
| volume | copies on the whole shelf | more than 2? |
|---|---|---|
| 3 | 1 | no, keep going |
| 7 | 3 | yes, return 7 |
The final return -1 in the code is never reached: LeetCode promises a majority.
Cost
- Time O(n x n): every book scans the whole shelf.
- Extra space O(1).
- On a 100,000-book shelf that is about 10,000,000,000 checks. The inner loop recounts the same volume every time it appears: 7 gets counted three times. The better ways remember instead.
public class MajorityBrute {
public static int majorityElement(int[] shelf) {
int size = shelf.length;
for (int volume : shelf) {
int copies = 0;
for (int book : shelf) {
if (book == volume) {
copies++;
}
}
if (copies > size / 2) {
return volume;
}
}
return -1;
}
public static void main(String[] args) {
int[] shelf = {3, 7, 7, 5, 7};
System.out.println("Majority: " + majorityElement(shelf));
}
}#include <bits/stdc++.h>
using namespace std;
int majorityElement(vector<int>& shelf) {
int size = (int) shelf.size();
for (int volume : shelf) {
int copies = 0;
for (int book : shelf) {
if (book == volume) {
copies++;
}
}
if (copies > size / 2) {
return volume;
}
}
return -1;
}
int main() {
vector<int> shelf = {3, 7, 7, 5, 7};
cout << "Majority: " << majorityElement(shelf) << endl;
return 0;
}def majority_element(shelf):
size = len(shelf)
for volume in shelf:
copies = 0
for book in shelf:
if book == volume:
copies += 1
if copies > size // 2:
return volume
return -1
shelf = [3, 7, 7, 5, 7]
print("Majority:", majority_element(shelf))function majorityElement(shelf) {
const size = shelf.length;
const half = Math.floor(size / 2);
for (const volume of shelf) {
let copies = 0;
for (const book of shelf) {
if (book === volume) {
copies++;
}
}
if (copies > half) {
return volume;
}
}
return -1;
}
const shelf = [3, 7, 7, 5, 7];
console.log("Majority: " + majorityElement(shelf));Better: Hash Map
Better: Hash Map Counting
Derive it under stress
- What am I doing again and again? The inner loop recounts the same volume every time it appears.
- What could I remember instead? How many copies of each volume I have seen so far.
- What remembers things by value? A hash map, from volume to number of copies:
copiesOf.
Pseudocode
majorityElement(shelf):
size = number of books in shelf
copiesOf = empty map, a missing volume counts as 0
for volume in shelf:
copiesOf[volume] = copiesOf[volume] + 1
if copiesOf[volume] > size / 2:
return volume
Why it works (proof)
copiesOf[volume]always holds how many copies ofvolumewe have seen so far.- The majority has more than half of the books, so at some point its count must pass half.
- Nothing else can pass half first: two volumes can’t both own more than half of the same shelf.
Dry run: shelf = [3, 7, 7, 5, 7], size = 5, so we need a count above 2
| volume | copiesOf after it | more than 2? |
|---|---|---|
| 3 | {3: 1} | no |
| 7 | {3: 1, 7: 1} | no |
| 7 | {3: 1, 7: 2} | no |
| 5 | {3: 1, 7: 2, 5: 1} | no |
| 7 | {3: 1, 7: 3, 5: 1} | yes, return 7 |
Cost
- Time O(n): one pass. A 100,000-book shelf takes 100,000 steps, not 10 billion.
- Extra space O(n): one entry per different volume.
Lines that confuse people
- Java
copiesOf.getOrDefault(volume, 0): the count for this volume, or 0 if it isn’t there yet. Pythoncopies_of.get(volume, 0)is the same. - C++
copiesOf[volume]++: a new key in anunordered_mapstarts at 0, so this just works. - JavaScript
(copiesOf.get(volume) || 0):getgivesundefinedfor a missing volume, and|| 0turns it into 0.Math.floor(shelf.length / 2)rounds down, because JavaScript division can leave decimals.
import java.util.HashMap;
public class MajorityHashMap {
public static int majorityElement(int[] shelf) {
int size = shelf.length;
HashMap<Integer, Integer> copiesOf = new HashMap<>();
for (int volume : shelf) {
int copies = copiesOf.getOrDefault(volume, 0) + 1;
copiesOf.put(volume, copies);
if (copies > size / 2) {
return volume;
}
}
return -1;
}
public static void main(String[] args) {
int[] shelf = {3, 7, 7, 5, 7};
System.out.println("Majority: " + majorityElement(shelf));
}
}#include <bits/stdc++.h>
using namespace std;
int majorityElement(vector<int>& shelf) {
int size = (int) shelf.size();
unordered_map<int, int> copiesOf;
for (int volume : shelf) {
copiesOf[volume]++;
if (copiesOf[volume] > size / 2) {
return volume;
}
}
return -1;
}
int main() {
vector<int> shelf = {3, 7, 7, 5, 7};
cout << "Majority: " << majorityElement(shelf) << endl;
return 0;
}def majority_element(shelf):
size = len(shelf)
copies_of = {}
for volume in shelf:
copies = copies_of.get(volume, 0) + 1
copies_of[volume] = copies
if copies > size // 2:
return volume
return -1
shelf = [3, 7, 7, 5, 7]
print("Majority:", majority_element(shelf))function majorityElement(shelf) {
const half = Math.floor(shelf.length / 2);
const copiesOf = new Map();
for (const volume of shelf) {
const copies = (copiesOf.get(volume) || 0) + 1;
copiesOf.set(volume, copies);
if (copies > half) {
return volume;
}
}
return -1;
}
const shelf = [3, 7, 7, 5, 7];
console.log("Majority: " + majorityElement(shelf));Optimal: Bit Counting
Optimal 1: Bit Counting (integers only)
Derive it under stress
- What costs me now? The table of counts. A million books with half a million different volumes fills the memory.
- Can I avoid keeping a count per volume? Every number is made of only 32 bits.
- Can I vote per bit instead? Yes: count the ones at each bit. A bit with more than half the votes belongs to the answer.
Pseudocode
majorityElement(shelf):
size = number of books in shelf
answer = 0
for bit from 0 to 31:
ones = 0
for volume in shelf:
if (volume >> bit) & 1 == 1:
ones = ones + 1
if ones > size / 2:
answer = answer with bit number "bit" turned on
return answer
(volume >> bit) & 1 reads one bit: the shift slides that bit to the end, and & 1 keeps only that last bit (0 or 1).
Why it works (proof)
Look at one bit. The majority has more than half of the books.
- If the majority has a 1 at this bit, its own copies already give more than half the ones. We count a 1 here.
- If it has a 0, more than half the books have a 0 here, so the ones can’t pass half. We count a 0.
Either way, the vote at each bit matches the majority’s bit.
Dry run: shelf = [3, 7, 7, 5, 7] (3 = 011, 7 = 111, 5 = 101), size = 5, so we need ones above 2
| bit | books with a 1 there | ones | answer so far |
|---|---|---|---|
| 0 | 3, 7, 7, 5, 7 | 5 | 001 |
| 1 | 3, 7, 7, 7 | 4 | 011 |
| 2 | 7, 7, 5, 7 | 4 | 111 |
| 3 to 31 | none | 0 | 111 = 7 |
Cost
- Time O(32 x n) = O(n): 32 passes over the shelf. 32 is a constant.
- Extra space O(1): a few variables. The shelf is never touched.
- Integers only. Titles (strings) have no fixed 32 bits to count.
Negative numbers (the sign bit)
- Java
intand JavaScript (|and<<work on 32-bit signed ints): turning bit 31 on gives the right negative number directly. - C++:
answeris anunsigned intand the shift is1u << bit, because shifting a 1 into the sign bit of a signedintis not safe. Cast back tointat the end. - Python:
>>on a negative number keeps its sign bits, so the votes are right, but ints have no fixed size. Ifanswer >= 2 ** 31, subtract2 ** 32to get the negative number back (all 32 ones, 4294967295, becomes -1).
public class MajorityBits {
public static int majorityElement(int[] shelf) {
int size = shelf.length;
int answer = 0;
for (int bit = 0; bit < 32; bit++) {
int ones = 0;
for (int volume : shelf) {
if (((volume >> bit) & 1) == 1) {
ones++;
}
}
if (ones > size / 2) {
answer = answer | (1 << bit);
}
}
return answer;
}
public static void main(String[] args) {
int[] shelf = {3, 7, 7, 5, 7};
System.out.println("Majority: " + majorityElement(shelf));
}
}#include <bits/stdc++.h>
using namespace std;
int majorityElement(vector<int>& shelf) {
int size = (int) shelf.size();
unsigned int answer = 0;
for (int bit = 0; bit < 32; bit++) {
int ones = 0;
for (int volume : shelf) {
if (((volume >> bit) & 1) == 1) {
ones++;
}
}
if (ones > size / 2) {
answer = answer | (1u << bit);
}
}
return (int) answer;
}
int main() {
vector<int> shelf = {3, 7, 7, 5, 7};
cout << "Majority: " << majorityElement(shelf) << endl;
return 0;
}def majority_element(shelf):
size = len(shelf)
answer = 0
for bit in range(32):
ones = 0
for volume in shelf:
if ((volume >> bit) & 1) == 1:
ones += 1
if ones > size // 2:
answer = answer | (1 << bit)
if answer >= 2 ** 31:
answer = answer - 2 ** 32
return answer
shelf = [3, 7, 7, 5, 7]
print("Majority:", majority_element(shelf))function majorityElement(shelf) {
const half = Math.floor(shelf.length / 2);
let answer = 0;
for (let bit = 0; bit < 32; bit++) {
let ones = 0;
for (const volume of shelf) {
if (((volume >> bit) & 1) === 1) {
ones++;
}
}
if (ones > half) {
answer = answer | (1 << bit);
}
}
return answer;
}
const shelf = [3, 7, 7, 5, 7];
console.log("Majority: " + majorityElement(shelf));Optimal: Boyer Moore Voting
Optimal 2: Boyer-Moore Voting
Derive it under stress (the books now have titles and roll past once, on a belt)
- What costs me, or breaks, now? Counting needs numbers, or a big table, or many passes.
- What can I throw away, and still keep the answer? Take two books with DIFFERENT volumes and send them away together. The majority survives (proof below).
- What small thing must I keep? Not the pairs. Only the one volume still waiting, and how many copies of it are waiting:
candidateandvotes.
Pseudocode
majorityElement(shelf):
candidate = nothing
votes = 0
for volume in shelf:
if votes == 0:
candidate = volume
if volume == candidate:
votes = votes + 1
else:
votes = votes - 1
return candidate
Same volume: votes up. Different volume: votes down (one pair is gone). Votes at zero: the next book becomes the candidate.
Why it works (proof)
Let m be the majority. It has more than half of the books.
- Take away a pair of DIFFERENT books. At most one of them is m. So m loses at most one copy, the shelf loses two books, and the half-line drops by one:
copies - 1 > (size - 2) / 2. m is still a majority of what is left. - Repeat until nothing different can be paired. Then only copies of one volume are left. A majority still exists in that group, so it is m.
- Pairs must be different. Two 7s leaving together would break the proof.
Dry run: shelf = [3, 7, 7, 5, 7]
| pass | volume | rule | candidate | votes |
|---|---|---|---|---|
| start | nothing | 0 | ||
| 1 | 3 | votes 0, so 3 becomes candidate; it matches | 3 | 1 |
| 2 | 7 | different: 3 and 7 leave as a pair | 3 | 0 |
| 3 | 7 | votes 0, so 7 becomes candidate; it matches | 7 | 1 |
| 4 | 5 | different: another pair leaves | 7 | 0 |
| 5 | 7 | votes 0, so 7 becomes candidate again | 7 | 1 |
The loop ends: candidate 7. The candidate switched, but the rules never lost the majority.
No majority promised? The verify pass (majorityOrNone, in the same code files)
(after the loop above)
count = number of books in shelf equal to candidate
if count > size / 2:
return candidate
else:
return none
Example [2, 2, 1, 1, 3, 1]: 6 books, and 1 has only 3 copies, not more than 3, so there is no majority. The walk ends with candidate 3. Boyer-Moore did not fail: when no majority exists, the candidate is only a guess. Count it: 1 copy, not more than 3, so no majority.
With no promise, “most common” is not enough either: in [4, 4, 1, 2, 3], 4 is the most common, but 2 copies is not more than 2.5.
The code returns -1 for “none” to stay short. Real code returns null (Java Integer), None (Python), null (JavaScript), or std::optional / a flag (C++), because -1 could be a real volume.
Cost
- Time O(n): one pass (two with verify).
- Extra space O(1): two variables. The shelf is never changed.
- Works on any type that can be compared for equality: numbers, titles, a stream you see once.
In an interview, say it in steps
- Count every volume: n x n.
- Remember counts in a hash map, or vote per bit: O(n).
- Pair off different books, keep a candidate and its votes: O(n) time, O(1) space.
- Trace a small example out loud.
Next: LeetCode 229 (more than n / 3)
Keep two candidates, each with its own votes. A book that matches neither cancels one vote from each (a triple leaves together); a new book fills an empty slot; always verify. More than n / k means k - 1 candidates.
public class MajorityMoore {
public static int majorityElement(int[] shelf) {
int candidate = 0;
int votes = 0;
for (int volume : shelf) {
if (votes == 0) {
candidate = volume;
}
if (volume == candidate) {
votes++;
} else {
votes--;
}
}
return candidate;
}
public static int majorityOrNone(int[] shelf) {
int size = shelf.length;
int candidate = majorityElement(shelf);
// ADDED: the verify pass
int count = 0;
for (int volume : shelf) {
if (volume == candidate) {
count++;
}
}
if (count > size / 2) {
return candidate;
}
return -1;
}
public static void main(String[] args) {
int[] shelf = {3, 7, 7, 5, 7};
System.out.println("Majority: " + majorityElement(shelf));
}
}#include <bits/stdc++.h>
using namespace std;
int majorityElement(vector<int>& shelf) {
int candidate = 0;
int votes = 0;
for (int volume : shelf) {
if (votes == 0) {
candidate = volume;
}
if (volume == candidate) {
votes++;
} else {
votes--;
}
}
return candidate;
}
int majorityOrNone(vector<int>& shelf) {
int size = (int) shelf.size();
int candidate = majorityElement(shelf);
// ADDED: the verify pass
int count = 0;
for (int volume : shelf) {
if (volume == candidate) {
count++;
}
}
if (count > size / 2) {
return candidate;
}
return -1;
}
int main() {
vector<int> shelf = {3, 7, 7, 5, 7};
cout << "Majority: " << majorityElement(shelf) << endl;
return 0;
}def majority_element(shelf):
candidate = 0
votes = 0
for volume in shelf:
if votes == 0:
candidate = volume
if volume == candidate:
votes += 1
else:
votes -= 1
return candidate
def majority_or_none(shelf):
size = len(shelf)
candidate = majority_element(shelf)
# ADDED: the verify pass
count = shelf.count(candidate)
if count > size // 2:
return candidate
return -1
shelf = [3, 7, 7, 5, 7]
print("Majority:", majority_element(shelf))function majorityElement(shelf) {
let candidate = 0;
let votes = 0;
for (const volume of shelf) {
if (votes === 0) {
candidate = volume;
}
if (volume === candidate) {
votes++;
} else {
votes--;
}
}
return candidate;
}
function majorityOrNone(shelf) {
const half = Math.floor(shelf.length / 2);
const candidate = majorityElement(shelf);
// ADDED: the verify pass
const count = shelf
.filter((volume) => volume === candidate)
.length;
if (count > half) {
return candidate;
}
return -1;
}
const shelf = [3, 7, 7, 5, 7];
console.log("Majority: " + majorityElement(shelf));