In-place array transform

How does In-place array transform work?

Two indices walk the same array. read visits every slot, write marks where the next kept value goes.

read moves on every step of the loop. write moves only when a value survives the test.

A kept value is copied to arr[write]. Then write advances by one slot.

A dropped value leaves write where it was. The next keeper will overwrite that slot.

write can never overtake read, so a copy never destroys unread data. That is why one buffer is enough.

At the end write holds the new logical length. The slots past it are leftovers.

1. [1, 1, 2, 2, 3] write=1 read=1Removing duplicates from a sorted array. The first value always survives.
2. [1, 1, 2, 2, 3] write=1 read=2arr[1] repeats arr[0] and is dropped. write does not move.
3. [1, 2, 2, 2, 3] write=2 read=3arr[2] is new, so it lands in slot 1. write advances.
4. [1, 2, 2, 2, 3] write=2 read=4arr[3] repeats the 2 already kept. It is dropped.
5. [1, 2, 3, 2, 3] write=33 lands in slot 2. The answer is length 3, and the tail is junk.

function inPlaceTransform(arr) {
    let write = 0;
    for (let read = 0; read < arr.length; read++) {
        if (shouldKeep(arr[read])) {
            arr[write] = arr[read];
            write++;
        }
    }
    return write; // new logical length
}

A worked example of In-place array transform

Move zeroes to the end

You get an array of numbers and have to move every zero to the end.

The order of the non-zero values must survive. Allocating a second array is not allowed.

Walk the array with a read index. Copy each non-zero value to arr[write] and advance write.

After the pass, write marks where the zeroes begin. Fill everything from there with zero.

function moveZeroes(nums) {
    let write = 0;

    for (let read = 0; read < nums.length; read++) {
        if (nums[read] !== 0) {
            nums[write] = nums[read];
            write++;
        }
    }

    // everything from write onwards is a leftover slot
    while (write < nums.length) {
        nums[write] = 0;
        write++;
    }

    return nums;
}

When should you use In-place array transform?

These phrases in a problem statement point here:

• •modify the array in place
• •O(1) extra space
• •do not allocate another array/string
• •reverse/rotate/partition/move elements over a single buffer
• •return the new length after removing duplicates

What is In-place array transform confused with?

• Two pointers (same direction): A slow and fast pair is one mechanic that rewrites a buffer. Working in place is the goal, not the mechanic.
• Hash set / map: A set drops duplicates in one pass but stores every key. In-place work exists to avoid that memory.
• Elementary sorts (selection, bubble, insertion): Insertion sort also rewrites one buffer, but it reorders values. Here the surviving order never changes.
• Prefix sums: Prefix sums build a second array of running totals. That second array is the thing being avoided.

Common mistakes with In-place array transform

• Advancing write on every step

  Then write and read stay equal and nothing is ever removed. write moves only on a keep.

• Cutting the tail during the pass

  The leftover slots still hold values read has not reached. Trim or overwrite them after the loop.

• Returning the array instead of the length

  These tasks usually ask for the new length. The buffer itself keeps its original size.

• Comparing against the wrong slot

  A duplicate check must read arr[write - 1], not arr[read - 1]. Earlier slots have already been rewritten.

Which interview problems use In-place array transform?

• Remove duplicates from sorted array: Keep a value only when it differs from arr[write - 1].
• Remove element: Keep everything that does not equal the target value.
• Move zeroes: Copy the non-zeroes forward, then pad the tail with zeroes.
• Sort colors: Three indices rewrite one buffer in a single pass.
• Rotate array: Reverse the whole array, then reverse each of the two parts.
• Reverse string: Swap from both ends inward with no new buffer.
• Remove duplicates from sorted array II: Keep a value while it differs from arr[write - 2].

What is the time and space complexity of In-place array transform?

O(n)

n up to 1e6 with a single pass gives O(n) time. Space stays O(1) because nothing new is allocated.