Introduction

Finding duplicates without extra space is a classic in-place array problem. It sounds universal, but these techniques only work when the input satisfies strict constraints about value range and mutability. The real task is not just detecting duplicates. It is matching the method to the guarantees you actually have.

Check the Preconditions First

Constant-extra-space duplicate detection usually assumes all of the following:

1. the array can be modified
2. values fall within a predictable range such as 1..n or 0..n-1
3. the caller accepts an in-place algorithm

If any of those conditions is false, a hash set or a sorted copy is often the correct solution instead. Interview-style tricks stop being safe the moment the input contract changes.

Sign Marking for Values in 1..n

One well-known technique uses the sign of each array element as a visited marker. When the value v appears, look at index v - 1. If that position is already negative, v is a duplicate.

1def find_duplicates_sign(nums):
2    duplicates = []
3
4    for i in range(len(nums)):
5        value = abs(nums[i])
6        index = value - 1
7
8        if nums[index] < 0:
9            duplicates.append(value)
10        else:
11            nums[index] = -nums[index]
12
13    return duplicates
14
15
16arr = [4, 3, 2, 7, 8, 2, 3, 1]
17print(find_duplicates_sign(arr.copy()))

This runs in linear time with constant extra space, but it mutates the signs in the array, so it is only valid when the caller allows that mutation.

Cyclic Placement for Values in 0..n-1

If values map naturally to indices, another approach is to swap each value toward its “correct” position. When the correct position already holds the same value, you found a duplicate.

1def find_duplicates_cyclic(nums):
2    duplicates = []
3    i = 0
4
5    while i < len(nums):
6        correct = nums[i]
7
8        if nums[i] != i and nums[i] != nums[correct]:
9            nums[i], nums[correct] = nums[correct], nums[i]
10        else:
11            if nums[i] != i and nums[i] == nums[correct] and nums[i] not in duplicates:
12                duplicates.append(nums[i])
13            i += 1
14
15    return duplicates
16
17
18arr = [2, 3, 1, 0, 2, 5, 3]
19print(find_duplicates_cyclic(arr.copy()))

This keeps extra space constant as well, but the logic is harder to reason about than the sign-marking version.

Modulo Counting Is Another Option

When values are guaranteed to stay in 0..n-1, you can encode counts by adding n to indexed positions. After the pass, division reveals how many times each value appeared.

1def find_duplicates_mod(nums):
2    n = len(nums)
3
4    for value in nums:
5        nums[value % n] += n
6
7    return [i for i, value in enumerate(nums) if value // n > 1]
8
9
10arr = [1, 2, 3, 1, 3, 6, 6]
11print(find_duplicates_mod(arr.copy()))

This method is clever, but in fixed-width integer languages it can introduce overflow risk. That is one reason it is less common in production code than in interviews.

Decide What the Output Means

Some callers want every repeated occurrence. Others want each duplicate value only once. Your function should document which one it returns. For example, the sign-marking approach above appends a duplicate every time the repeated value is encountered after the first appearance.

If you need each duplicate only once, deduplicate the output or adapt the algorithm accordingly. That should be part of the function contract, not a surprise that callers discover later.

Restore the Array Only if Needed

These algorithms are attractive because they avoid extra memory, but they often damage the original array contents. If the original data must be preserved, either restore it afterward or choose a different method entirely.

def restore_signs(nums):
    for i in range(len(nums)):
        nums[i] = abs(nums[i])

Restoring can be cheap for sign-based methods and more awkward for swap-based methods. That tradeoff should be part of the design decision.

Common Pitfalls

The most common mistake is applying an in-place trick without validating the required value range. Another is mutating an array that the rest of the program expected to remain unchanged. Developers also forget to define whether duplicates should be returned once or multiple times, which makes integration behavior inconsistent.

Summary

• Duplicate detection without extra space works only under strict input constraints.
• Sign marking is simple and effective for arrays with values in 1..n.
• Cyclic placement and modulo counting also work, but they require careful preconditions.
• In-place methods trade readability and mutability for lower memory use.
• Always document the expected value range, mutation behavior, and duplicate-output semantics.