LearnWithKiriti

Majority Element I

đź’» Try it yourself first. Write your solution in Java, C++, Python or JavaScript and run it against hidden tests, right here.
Play
On this page
  1. Revision notes
  2. Brute
  3. Better: Hash Map
  4. Optimal: Bit Counting
  5. Optimal: Boyer Moore Voting

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

  1. What would I do by hand, on a tiny example?
  2. What is the dumbest thing that works? (brute force)
  3. 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 int and JavaScript | are 32-bit signed, so turning bit 31 on gives the right negative number.
    • C++ builds answer as an unsigned int (shifting a 1 into the sign bit of a signed int is not safe), then casts back to int.
    • Python ints have no fixed size, so answer can reach 2 ** 31 or more. Subtract 2 ** 32 to get the negative number back.
  • 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

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.
MajorityBrute.java
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));
    }
}
better

Better: Hash Map

Better: Hash Map Counting

Derive it under stress

  1. What am I doing again and again? The inner loop recounts the same volume every time it appears.
  2. What could I remember instead? How many copies of each volume I have seen so far.
  3. 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 of volume we 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. Python copies_of.get(volume, 0) is the same.
  • C++ copiesOf[volume]++: a new key in an unordered_map starts at 0, so this just works.
  • JavaScript (copiesOf.get(volume) || 0): get gives undefined for a missing volume, and || 0 turns it into 0. Math.floor(shelf.length / 2) rounds down, because JavaScript division can leave decimals.
MajorityHashMap.java
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));
    }
}
optimal

Optimal: Bit Counting

Optimal 1: Bit Counting (integers only)

Derive it under stress

  1. What costs me now? The table of counts. A million books with half a million different volumes fills the memory.
  2. Can I avoid keeping a count per volume? Every number is made of only 32 bits.
  3. 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 int and JavaScript (| and << work on 32-bit signed ints): turning bit 31 on gives the right negative number directly.
  • C++: answer is an unsigned int and the shift is 1u << bit, because shifting a 1 into the sign bit of a signed int is not safe. Cast back to int at the end.
  • Python: >> on a negative number keeps its sign bits, so the votes are right, but ints have no fixed size. If answer >= 2 ** 31, subtract 2 ** 32 to get the negative number back (all 32 ones, 4294967295, becomes -1).
MajorityBits.java
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));
    }
}
optimal

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)

  1. What costs me, or breaks, now? Counting needs numbers, or a big table, or many passes.
  2. 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).
  3. What small thing must I keep? Not the pairs. Only the one volume still waiting, and how many copies of it are waiting: candidate and votes.

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

  1. Count every volume: n x n.
  2. Remember counts in a hash map, or vote per bit: O(n).
  3. Pair off different books, keep a candidate and its votes: O(n) time, O(1) space.
  4. 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.

MajorityMoore.java
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));
    }
}