The O(n) Club: Number of Good Pairs – Because Nested Loops Deserve Retirement

The O(n) Club: Number of Good Pairs – Because Nested Loops Deserve Retirement

⚡ TL;DR

Count (i, j) with nums[i] == nums[j] and i < j—instead of double looping. Just count how many times you’ve already seen a number when you see it again. Java makes it a one-liner (almost) if you squint hard enough:

int goodPairs = 0;
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
    goodPairs += freq.getOrDefault(num, 0);
    freq.put(num, freq.getOrDefault(num, 0) + 1);
}

🧠 How Devs Usually Mess This Up

Some devs see “pair” and instantly break out two for-loops like it’s 1998. Sure, it’s correct, but so is a horse-drawn carriage—just slower, and sweatier. Bonus: Sometimes people neglect i < j, and their output is basically a bug generator.

🔍 What’s Actually Going On

Think of yourself in a mascot costume at a stadium. Every identical mascot entering after you is a new “good pair” with you; every time someone walks in wearing your getup, you just add all their previous matching buddies to the total. Frequency counting is your backstage pass to linear time glory.

🛠️ PseudoCode

• Make a frequency map: Map to count how many times we’ve seen each number.
• Walk the array left-to-right:
  • For each num, increment answer by freq[num] (the number of times we’ve already seen num).
  • Then increase freq[num] by 1 (because now we’ve seen it one more time).
• Return the answer. That’s it—nobody got hurt.

💻 The Code

public int numIdenticalPairs(int[] nums) {
    int goodPairs = 0;
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        goodPairs += freq.getOrDefault(num, 0);
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }
    return goodPairs;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• All Same? With 10,000 identical elements, you’ve got almost 50 million pairs. Integer overflow says hello.
• Speed Run: If values are small and positive (like 1-100), just use int[] freq = new int[101] and leave HashMap at home.
• Space/Time: O(n), so your CPU only starts sweating on pizza day.

🧠 Interviewer Brain-Tattoo

“Every time a number reappears, it’s shaking hands with all its previous twin siblings. Count handshakes, not heads.”