The O(n) Club: Majority Element II and the Pigeonhole Plot Twist

The O(n) Club: Majority Element II and the Pigeonhole Plot Twist

⚡ TL;DR

Need to spot every array element that appears more than n/3 times? No, you can’t collect the whole set—there can be at most two. Brute-force it with HashMaps if you’re feeling retro, but an interviewer’s eyebrow will reach escape velocity. See below for a basic (but boring) way:

// Brute force: so last season...
Map<Integer, Integer> counts = new HashMap<>();
for (int num : nums) counts.put(num, counts.getOrDefault(num, 0) + 1);
List<Integer> res = new ArrayList<>();
for (int key : counts.keySet())
  if (counts.get(key) > nums.length / 3) res.add(key);
return res;

🧠 How Devs Usually Mess This Up

Most folks bust out a HashMap to count everything (hello, O(n) space), or forget only two elements can break the n/3 barrier. Some try classic Boyer-Moore—which is great!—except it only grabs a single candidate, not two. Others forget The Validation Pass™: their dearly beloved candidates might just be photobombers.

🔍 What’s Actually Going On

Imagine an exclusive club with three velvet-rope rooms but only two bottles of champagne to hand out. The pigeonhole principle guarantees: you can’t have three party animals each outnumbering a third of the crowd. Our extension of Boyer-Moore now plays bouncer for two guests/candidates, and you still have to do a quick headcount at the end. Because—big twist—sometimes the supposed rockstars sneak in and out without making the attendance cut.

🛠️ PseudoCode

• Set two variables for candidate1 and candidate2; set two counters to zero.
• First pass through the array:
  • If number matches candidate1, increment count1.
  • Else if it matches candidate2, increment count2.
  • Else if count1 zero? Make this candidate1, set count1 = 1.
  • Else if count2 zero? Make this candidate2, set count2 = 1.
  • Else? Both counts down by one (because some partygoer brought a friend nobody knows).
• Second pass: Actually count how often candidate1 and candidate2 occur. (Sorry, impostors!)
• Add whichever candidates truly appear more than n/3 times to your glorious result list.

💻 The Code

public List<Integer> majorityElement(int[] nums) {
    int candidate1 = 0, candidate2 = 1; // cannot start the same!
    int count1 = 0, count2 = 0;
    for (int num : nums) {
        if (num == candidate1) count1++;
        else if (num == candidate2) count2++;
        else if (count1 == 0) { candidate1 = num; count1 = 1; }
        else if (count2 == 0) { candidate2 = num; count2 = 1; }
        else { count1--; count2--; }
    }
    // Validate or risk electing a mannequin
    count1 = count2 = 0;
    for (int num : nums) {
        if (num == candidate1) count1++;
        else if (num == candidate2) count2++;
    }
    List<Integer> out = new ArrayList<>();
    if (count1 > nums.length / 3) out.add(candidate1);
    if (count2 > nums.length / 3) out.add(candidate2);
    return out;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• More than two “majority” elements? Not unless your array is from a parallel dimension.
• Skip the validation pass and you’ll end up with randoms in your result.
• Edge cases:
  • Empty array? Returns nothing, like your last sprint review.
  • All elements the same? Just one result, don’t be greedy.
  • Appear exactly n/3 times? Not enough. The bar is higher—‘strictly more than’.
• Runtime: Two quick strolls over the array. Space? Only your two VIP counters—no guest lists.

🧠 Interviewer Brain-Tattoo

“Two buckets, two winners. Try to track a third? You’re chasing algorithmic shadows.”

And if they ask about k buckets…just smile, and hand them a marker.