The O(n) Club: Find-All-Duplicates—No HashMaps, No Regrets

The O(n) Club: Find-All-Duplicates—No HashMaps, No Regrets

⚡ TL;DR

Given an array stuffed with numbers from 1 to n, some appear once, some twice, and you want the repeat offenders—no HashMaps, no sorting, memory hoarder.
Here’s a Java one-liner for the negative-marking trick, perfect for anyone allergic to extra space:

// Negative Marking - O(n) time, O(1) space
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
    int idx = Math.abs(nums[i]) - 1;
    if (nums[idx] < 0) result.add(idx + 1);
    nums[idx] = -Math.abs(nums[idx]);
}

🧠 How Devs Usually Mess This Up

No shame—most reach for HashMap<Integer, Integer> faster than you can say “O(1) space.” Some bold souls try sorting, then hope nobody notices the memory or time cost. Both get you an interviewer eyebrow raise and a silent ding on your record…

Remember: no extra space allowed. Sorting isn’t as “free” as Java wants you to believe, and hash maps? Forbidden fruit.

🔍 What’s Actually Going On

Here’s the chef’s kiss: Since all numbers are in [1, n], every value is basically pointing at an array locker where it “belongs.” If you visit a locker and it’s already negative, you’ve met its owner before—hello, duplicate!
There are two spicy flavors to try:

• Negative Marking: Sign-flip means “been here.” On the second visit, it’s already negative—party crasher caught.
• Cyclic Sort: Hot-potato swap each value to its correct index. Duplicates are those that bump into a twin already sitting pretty.

🛠️ PseudoCode

• Loop through array from 0 to n-1:
  • For nums[i], take its absolute value: call it num.
• Map num to index: idx = num - 1
• If nums[idx] is negative, you’ve visited before—record num as a duplicate
• Otherwise, mark nums[idx] as visited by negating it
• Collect the crimes (numbers that appeared twice) in your result list

💻 The Code

import java.util.*;
 public class FindDuplicates {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int idx = Math.abs(nums[i]) - 1;
            if (nums[idx] < 0) res.add(idx + 1);
            nums[idx] = -Math.abs(nums[idx]);
        }
        return res;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Modifies Input: Don’t expect your array to come out unscathed. Back it up if you care.
• Time Complexity: Each element is checked and maybe negated twice. O(n) for “n” coffee breaks per entry.
• Space Complexity: Output list only. Less memory used than your IDE.
• Triple Duplicates? Not allowed, per the problem. But if you code this for a wild array—test carefully.
• Negative Numbers? Not in this playpen; all inputs are [1, n]. If you see negatives at the start, blame your test data or cosmic rays.

🧠 Interviewer Brain-Tattoo

“Why use a HashMap when you’ve got index access and attitude?” No extra memory, just a dash of in-place mischief.