In-Place Array Manipulation — Negation Marking

Before we start

By the end of this page you will be able to:

• See why flipping a number negative is a reversible "sticky note" on the array itself.
• Explain out loud why this always uses O(1) extra space even when tracking many visited positions.
• Recognise this trick in "find duplicates," "find the disappeared," and "find the corrupt pair" problems when the constraint is O(1) space.

Stop at every Pause & Think box.

Picture this first (no code yet)

The hotel inspector's trick — mark by flipping, read original with abs() — is the negation marking pattern.

The actual problem

You are given an array of length N where every value is in [1, N]. Some values appear twice, some appear once. Find all values that appear twice, in O(n) time and O(1) extra space.

input  : [4, 3, 2, 7, 8, 2, 3, 1]
output : [2, 3]

No hash set. No extra array. Just the input itself.

First, the slow way (so you feel the pain)

With a hash set: O(n) time, O(n) space — straightforward but violates the space constraint.

seen = set()
duplicates = []
for x in arr:
    if x in seen:
        duplicates.append(x)
    else:
        seen.add(x)

Sort first: O(n log n) time — also violates the constraint that we shouldn't modify order (and it's slower).

The negation approach is O(n) time and O(1) space — the best possible for both simultaneously.

The turning point

The values in the array are in [1, N], and the indices are 0 to N-1. Value v and index v - 1 are linked.

The key question: can we use the array itself to record "I have seen value v" — without using extra memory?

Flip it negative. Index 2 holds the value 2. After marking: -2. When you later read index 2, abs(-2) = 2 — the original value is perfectly preserved. The sign is your sticky note.

When you encounter value v:

1. Compute index idx = abs(v) - 1 (use abs because a previous step might have already flipped v itself).
2. Look at arr[idx]. If it's already negative — someone visited index idx before, meaning value idx + 1 was seen twice. Duplicate found.
3. If it's positive — first time visiting. Flip: arr[idx] = -arr[idx].

The one idea to remember

Watch it happen, frame by frame

Array: [4, 3, 2, 7, 8, 2, 3, 1]. Indices 0–7.

i=0: value=4. idx=3. arr[3]=7>0 → mark: arr[3]=-7.
     Array: [4, 3, 2,-7, 8, 2, 3, 1]

i=1: value=3. idx=2. arr[2]=2>0 → mark: arr[2]=-2.
     Array: [4, 3,-2,-7, 8, 2, 3, 1]

i=2: value=-2. abs(-2)=2. idx=1. arr[1]=3>0 → mark: arr[1]=-3.
     Array: [4,-3,-2,-7, 8, 2, 3, 1]

i=3: value=-7. abs(-7)=7. idx=6. arr[6]=3>0 → mark: arr[6]=-3.
     Array: [4,-3,-2,-7, 8, 2,-3, 1]

i=4: value=8. idx=7. arr[7]=1>0 → mark: arr[7]=-1.
     Array: [4,-3,-2,-7, 8, 2,-3,-1]

i=5: value=2. idx=1. arr[1]=-3<0 → ALREADY MARKED. 2 is a DUPLICATE ✓

i=6: value=-3. abs(-3)=3. idx=2. arr[2]=-2<0 → ALREADY MARKED. 3 is a DUPLICATE ✓

i=7: value=1. idx=0. arr[0]=4>0 → mark: arr[0]=-4.
     Array: [-4,-3,-2,-7, 8, 2,-3,-1]

Result: [2, 3]  ✅

i=0: value=1. idx=0. arr[0]=1>0 → mark: arr[0]=-1.
     Array: [-1, 1, 2]

i=1: value=1. idx=0. arr[0]=-1<0 → ALREADY MARKED. 1 is a DUPLICATE ✓

i=2: value=2. idx=1. arr[1]=1>0 → mark: arr[1]=-2.
     Array: [-1,-2, 2]

Result: [1]  ✅

Now, the code — line by line

def findDuplicates(nums):
    duplicates = []

    for v in nums:
        idx = abs(v) - 1           # value v maps to index v-1; abs() handles already-flipped values

        if nums[idx] < 0:          # already negative = already visited = DUPLICATE
            duplicates.append(idx + 1)
        else:
            nums[idx] = -nums[idx] # first visit — flip negative as a marker

    return duplicates

Every line mapped to the hotel story:

• idx = abs(v) - 1 — read the room number from the keycard (abs handles already-upside-down cards).
• if nums[idx] < 0: — is the keycard for room idx+1 already upside-down (visited)?
• duplicates.append(idx + 1) — yes: this room was already inspected → the value idx + 1 appeared before.
• nums[idx] = -nums[idx] — no: first visit → flip the keycard upside-down.

Why is this always correct?

The mapping is bijective: value v ↔ index v-1. For each value v seen, we write a marker at a unique index. Two values never write to the same index (unless they're duplicates of each other). Reading abs(nums[idx]) always recovers the original value regardless of how many times the sign has been flipped.

Time: O(n) — one pass through the array. Space: O(1) — no extra data structures; we use the input array itself as the marking board.

When should I reach for this? (the trigger list)

Reach for negation marking when:

• Values are in the range [1, N] (so they map cleanly to indices [0, N-1]).
• You need to detect duplicates or missing values in O(1) extra space.
• A hash set would solve it but the problem forbids O(n) extra memory.
• The problem says "do not use extra space" or "use the input array itself."
• You already know Cyclic Sort (1.12) — negation marking is its complement: Cyclic Sort moves values to their homes; negation marking marks homes in-place without moving values.

The same trick in three disguises

Disguise 1 — Find All Numbers Disappeared (LC #448)

Same array [1,N], but now report which values are missing (never appeared, so their corresponding index was never marked negative).

def findDisappearedNumbers(nums):
    for v in nums:
        idx = abs(v) - 1
        if nums[idx] > 0:
            nums[idx] = -nums[idx]   # mark visited

    # Any index still positive → its value (idx+1) never appeared
    return [i + 1 for i in range(len(nums)) if nums[i] > 0]

Same marking pass. Different final scan: look for positive indices (unvisited), not negative ones (visited twice).

Disguise 2 — Set Mismatch (LC #645): missing and duplicate together

One value appears twice; one value is missing. One pass finds the duplicate; the second scan finds the unvisited index.

def findErrorNums(nums):
    duplicate = -1
    for v in nums:
        idx = abs(v) - 1
        if nums[idx] < 0:
            duplicate = idx + 1      # already negative → duplicate
        else:
            nums[idx] = -nums[idx]

    missing = next(i + 1 for i in range(len(nums)) if nums[i] > 0)
    return [duplicate, missing]

Disguise 3 — First Missing Positive (LC #41) with negation

Values outside [1, N] can't be used as indices — clean them out first by setting to N+1 (a sentinel), then use negation marking for the valid values.

def firstMissingPositive(nums):
    n = len(nums)
    # Step 1: replace out-of-range values with a sentinel
    for i in range(n):
        if nums[i] <= 0 or nums[i] > n:
            nums[i] = n + 1

    # Step 2: mark using negation
    for v in nums:
        idx = abs(v) - 1
        if idx < n and nums[idx] > 0:
            nums[idx] = -nums[idx]

    # Step 3: first unvisited index → first missing positive
    for i in range(n):
        if nums[i] > 0:
            return i + 1
    return n + 1

Traps that catch beginners

Say it like a pro (interview one-liner)

"Since values are in [1, N], they map directly to indices [0, N-1]. I'll use the sign of each indexed cell as a boolean flag — flip it negative to mark 'visited.' When I land on an already-negative cell, that value appeared before: it's a duplicate. abs() always recovers the original value, so the marking is fully reversible. O(n) time, O(1) space, one pass."

Check yourself

Practice problems

When you can write the abs(v) - 1 indexing from memory and explain why abs is non-negotiable, you've learned this pattern.

Next up: Subarray Counting with Prefix Sums — where a running total and a hash map together count subarrays in a single pass.