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.

Sources: Wikipedia: In-place algorithm

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
}

declare function shouldKeep(value: number): boolean;

function inPlaceTransform(arr: number[]): number {
    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
}

def in_place_transform(arr):
    write = 0
    for read in range(len(arr)):
        if should_keep(arr[read]):
            arr[write] = arr[read]
            write += 1
    return write  # new logical length

function inPlaceTransform(array &$arr): int {
    $write = 0;
    for ($read = 0; $read < count($arr); $read++) {
        if (shouldKeep($arr[$read])) {
            $arr[$write] = $arr[$read];
            $write++;
        }
    }
    return $write; // new logical length
}

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

    private static boolean shouldKeep(int value) {
        throw new UnsupportedOperationException("your rule here");
    }

    public static int InPlaceTransform(int[] arr) {
        int write = 0;
        for (int read = 0; read < arr.Length; read++) {
            if (ShouldKeep(arr[read])) {
                arr[write] = arr[read];
                write++;
            }
        }
        return write; // new logical length
    }

    private static bool ShouldKeep(int value) {
        throw new NotImplementedException("your rule here");
    }

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?

Use In-place array transform when the problem statement says “modify the array in place”, “O(1) extra space” or “do not allocate another array/string”. A solution built on it usually runs in O(n).

• •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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is In-place array transform confused with?

In-place array transform is most often confused with Two pointers (same direction), Hash set / map, Elementary sorts (selection, bubble, insertion) and Prefix sums.

• 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

  Moving write on every step keeps it equal to read, so nothing is 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?

Interview problems solved with In-place array transform include Remove duplicates from sorted array, Remove element, Move zeroes, Sort colors, Rotate array, Reverse string and Remove duplicates from sorted array II.

• 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?

The target complexity of In-place array transform is O(n).

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