Given an integer array of size n where values range from 1 to n, and at least one duplicate exists, find every repeated number. The naive solution uses a hashmap. The interesting solution uses the array itself.
The trick relies on the input constraint. If values fit in [1, n], you can use the value as an index. Walk through the array, flip signs, and any value whose target index is already negative is a duplicate.
How the hashmap approach works
Count frequencies in a dictionary. Walk through it, collect keys with count of 2 or more. Done. It is correct, easy to read, and uses O(n) extra space.
That last bit is the cost. For small arrays, irrelevant. For large arrays in memory-constrained contexts, that extra allocation can matter.
This is also the version most candidates reach for first in interviews. Fine. Mention it, then offer the in-place version.
How the sign-flipping trick works
Because every value is between 1 and n, you can use each value as a pointer to an array index. Take absolute value, subtract 1, look at the element at that index.
If it is positive, flip it to negative. You have now "marked" that index as visited. If it is already negative, you have seen this value before. That is your duplicate.
The array is modified in the process. If that matters, copy it first.
When to use which: A quick decision guide
| Scenario | Recommended Approach | Why |
|---|---|---|
| General production code | Hashmap | Readable, maintainable, easy to extend |
| Memory-constrained environments | Sign-flipping | O(1) extra space |
| Need to preserve input | Hashmap or count array | No mutation required |
| Frequent duplicate checks | Count array | Better cache locality than hashmap |
The hashmap version is the right default. It is easier to reason about, easier to debug, and easier to extend if the input constraint changes. Most production code should use it.
The sign-flipping version is the right answer when space is explicitly constrained, or when you are working in a context where memory is genuinely tight. Embedded systems, kernel code, or hot loops in performance-sensitive code qualify. Most web app code does not.
A third option exists. A count array of size n uses O(n) space but is faster than a hashmap due to cache locality. If the constraint is "use less memory than a hashmap but I do not want to mutate the input," this is the middle ground.
Worked example: the sign-flipping trick in action
Say you have the array [5, 3, 4, 2, 5, 1, 2]. Walk through with the sign-flipping trick.
Index 0, value 5. Look at index 4. Value there is 2, flip to -2.
Index 1, value 3. Look at index 2. Value there is 4, flip to -4.
Index 2, value 4. Look at index 3. Value there is 2, flip to -2.
Index 3, value 2. Look at index 1. Value there is 3, flip to -3.
Index 4, value 5. Look at index 4. Value there is -2 already. Duplicate found: 5.
Index 5, value 1. Look at index 0. Value there is 5, flip to -5.
Index 6, value 2. Look at index 1. Value there is -3 already. Duplicate found: 2.
Output: 5, 2. Correct.
What to watch next
This pattern shows up in several interview classics: find the missing number, find all duplicates, find the disappeared numbers. All of them rely on the same constraint that values fit in [1, n]. Learn one, learn them all.
Implementations are provided in C++, Java, and Python. Read them side by side to see how the sign-flipping trick translates across languages.
Key takeaways
- Use a hashmap when readability matters more than memory
- Use the sign-flipping trick when you need O(1) extra space
- The trick only works because input values are guaranteed to be in [1, n]
- The count array offers a middle ground between memory and performance
Frequently asked questions
What is the time complexity of the sign-flipping approach?
O(n) time. Each element is visited once, and the array operations are constant time.
Does the sign-flipping approach modify the input?
Yes. Elements are negated as you go. Copy the array first if you need the original.
Can I use this if values can be negative?
No. The trick relies on values being in [1, n]. Use the hashmap approach for unrestricted inputs.
What if no duplicates exist?
The problem statement guarantees at least one duplicate. Without that guarantee, the sign-flipping version returns an empty set, which is correct behaviour.
Why not just use a boolean array instead of sign-flipping?
A boolean array of size n uses O(n) space, which defeats the purpose of the O(1) space trick. Sign-flipping reuses the input array itself as the marker, avoiding any extra allocation.