When I first saw LeetCode 442 — Find All Duplicates in an Array, my initial thought was:
“Okay, I’ll just use a set to track occurrences.”
But then I came across Index Marking, and it blew my mind! 🤯 This method lets you find duplicates in O(n) time using O(1) extra space — without sorting or extra data structures.
How Does It Work?
Instead of storing visited numbers in a set, we mark them directly in the array:
1️⃣ Treat each number as an index.
2️⃣ Flip the sign of the number at that index (to mark it).
3️⃣ If we encounter a negative number, it means the index has been visited before → it’s a duplicate!
Example Walkthrough
📌 Given array: [4, 3, 2, 7, 8, 2, 3, 1]
Read 4 → Mark Index 3 (nums[3] = -7)
Read 3 → Mark Index 2 (nums[2] = -2)
Read 2 → Mark Index 1 (nums[1] = -3)
Read 7 → Mark Index 6 (nums[6] = -3)
Read 8 → Mark Index 7 (nums[7] = -1)
Read 2 → Index 1 It's already negative → Duplicate!
Read 3 → Index 2 It's already negative → Duplicate!
Why This Works
✔️ O(n) time complexity (each number is processed once)
✔️ O(1) space complexity (modifies input array instead of using extra space)
✔️ Avoids sorting (which takes O(n log n) time)
Takeaway
This trick is a game-changer for space-efficient duplicate detection! If you haven’t tried it yet, give it a shot next time you see a similar problem.
Top comments (0)