In-place techniques

Big idea

"In place" means rearranging the array inside its own memory, using a few index variables instead of a second array. Three moves cover most of these problems: swap from both ends, overwrite with a write pointer, and reverse in pieces.

Move 1: swap from both ends (reverse)

def reverse(arr, lo, hi):
    while lo < hi:
        arr[lo], arr[hi] = arr[hi], arr[lo]
        lo += 1
        hi -= 1

n/2 swaps, two integers of extra space. lo and hi are inclusive, so reverse(arr, 0, len(arr) - 1) reverses everything.

Move 2: a write pointer (filter in place)

To keep only some items, walk a read index over everything and a write index that marks where the next kept item goes:

def remove_value(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    return write            # the first `write` slots are the answer

Trace nums = [3, 2, 2, 3], val = 3:

Result: the first 2 slots, [2, 2]. write never passes read, so we never overwrite something we haven't read yet. The same skeleton does Move Zeroes (then fill the tail with zeros) and Remove Duplicates from Sorted Array (keep an item if it differs from the last kept one). Those live in two pointers.

Watch it

Move 3: reverse in pieces (rotate)

Rotate [1, 2, 3, 4, 5, 6, 7] right by k = 3 to get [5, 6, 7, 1, 2, 3, 4]. Copying into a new array is easy; in place, use three reversals:

reverse all:          [7, 6, 5, 4, 3, 2, 1]
reverse first k=3:    [5, 6, 7, 4, 3, 2, 1]
reverse the rest:     [5, 6, 7, 1, 2, 3, 4]

def rotate(nums, k):
    n = len(nums)
    k %= n                      # rotating by n is a no-op
    reverse(nums, 0, n - 1)
    reverse(nums, 0, k - 1)
    reverse(nums, k, n - 1)

O(n) time, O(1) space. Don't forget k %= n — k can be larger than the array.

Move 4: the array as its own hash map

When values are in the range 1..n, the array's indices can act as a lookup table. To mark that value v was seen, negate nums[v - 1]; a slot still positive at the end means its value was missing. Cyclic sort builds a whole topic on this idea.

Before you modify the input

In an interview, say it out loud: "Can I modify the input array?" If the caller still needs it, in-place tricks are off the table (or you copy first, losing the O(1) space).

Practice

• Rotate Array — three reversals.
• Next Permutation — find a pivot, swap, then reverse the suffix.
• Majority Element — a single counter instead of a map (Boyer–Moore voting).

Quick check