In-place array tricks

Problem

Many array questions end with "do it in place" or "use O(1) extra space". Copying into a new list would be easy; the constraint forces you to find a place in the array itself to keep your work. The skill is to know which part of the array is already safe to overwrite.

Intuition

Picture a conveyor belt with a worker standing at a gap. The worker looks at the item arriving, and either lets it pass or slides it into the gap and moves the gap along. The gap is always behind the item being inspected, so the worker never knocks over something they have not looked at yet. That is the read and write index pair.

For rotations, picture reversing a line of people, and then reversing each of the two groups that moved: each group is back in its original internal order, just on the opposite side. For the cyclic trick, picture coat hooks numbered 1 to n: if each coat has a number, hang it on its own hook, and any empty or wrong hook at the end reveals what is missing.

Amber values are never copied; the green prefix is the answer.

Mechanics

Read and write indices

Keep two indices. read scans every position; write is the next slot of the output. The invariant: nums[:write] is exactly the answer for nums[:read], and write ≤ read. The second half matters for safety: because write never gets ahead of read, assigning nums[write] = nums[read] only overwrites cells that have already been read. Each step either keeps the value (copy, then advance write) or drops it (do nothing). When read reaches the end, write is the new length.

Rotation by three reversals

Rotating right by k moves the last k elements to the front, keeping the order within both groups. Reversing the whole array puts those k elements at the front but backwards; reversing the first k puts them back in order, and reversing the remaining n − k does the same for the rest. Always reduce k modulo n first, or k larger than n walks off the array.

Next permutation

Arrangements in dictionary order share longer and longer prefixes, so the next one changes as short a tail as possible. Scan from the right for the first position (the pivot) whose value is smaller than its right neighbour: everything to the right of it is non-increasing, so that suffix is already the largest arrangement of its values and cannot go up. Swap the pivot with the smallest suffix value that is larger than it, which makes the prefix as small a step up as possible. The suffix is still non-increasing, so reversing it gives its smallest order. If there is no pivot, the whole array is the last permutation and the answer is its reverse.

Cyclic placement

If the values are known to lie in 1..n, value v has exactly one home, index v − 1. For each index, while the value there is in range and its home does not already hold that value, swap it into its home. Each swap places at least one value permanently, so the total number of swaps is at most n and the whole pass is O(n) even with the inner loop. Afterwards the first index i where nums[i] != i + 1 means i + 1 is missing; if none, n + 1 is. The check for "home already holds it" is also what makes duplicates safe: without it, two equal values would swap forever.

Colour tracks the three values that end up in front: backwards after the first reversal, in order after the second.

Worked example

Removing the value 2 from [3, 2, 2, 3, 4, 2, 5]. After each read the table shows the write index and the array's front.

The new length is 4 and the kept prefix is [3, 3, 4, 5]. Note that the tail of the array still holds stale values; the problem only asks for the prefix.

Rotation. Rotating [1, 2, 3, 4, 5, 6, 7] right by 3:

Next permutation of [1, 3, 5, 4, 2]: the pivot is index 1 (value 3, smaller than its right neighbour 5). The smallest larger value in the non-increasing suffix is 4 at index 3. Swapping gives [1, 4, 5, 3, 2]; reversing the suffix after the pivot gives [1, 4, 2, 3, 5].

Each swap fixes at least one value for good, so the pass cannot loop.

Cyclic placement on [3, 4, -1, 1] takes 3 swaps and leaves [1, -1, 3, 4]. The first index whose value is not index + 1 is 1, so the missing positive is 2. Negative values and values above n are simply ignored.

Implementation

def remove_value(nums, val):                    # returns new length
    write = 0
    for x in nums:
        if x != val:
            nums[write] = x
            write += 1
    return write


def rotate(nums, k):                            # right by k, in place
    n = len(nums)
    k %= n

    def reverse(lo, hi):                        # inclusive bounds
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo += 1
            hi -= 1

    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)


def next_permutation(nums):
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1                                  # pivot
    if i >= 0:
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1:] = reversed(nums[i + 1:])       # i == -1 reverses everything


def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            home = nums[i] - 1
            nums[i], nums[home] = nums[home], nums[i]
    return next((i + 1 for i in range(n) if nums[i] != i + 1), n + 1)


def encode(strs):
    return "".join(f"{len(s)}#{s}" for s in strs)


def decode(text):
    out, i = [], 0
    while i < len(text):
        j = text.index("#", i)
        size = int(text[i:j])
        out.append(text[j + 1:j + 1 + size])
        i = j + 1 + size
    return out

Variations and edge cases

• Move zeroes. The same write index, but after the scan fill the rest with zeros, or swap instead of copy so the zeros accumulate behind the write index automatically.
• Remove duplicates from a sorted array. Keep a value when it differs from the last one written (nums[write - 1]), the invariant being that the prefix has no duplicates.
• Merge from the back. When the destination has spare room at the end, fill it from the largest element down; the write index then trails behind the unread values.
• Sign marking. For values in 1..n, flip the sign at index v − 1 to record "v seen", using the sign bit as the hash set. Read the absolute value when scanning, or you will treat a mark as data.
• Edge cases: k = 0 or k a multiple of n in rotation, a single-element array, an all-descending array for next permutation, duplicates in cyclic placement (the home check), zero or negative values, and strings that themselves contain your delimiter (hence the length prefix).

Complexity and tradeoffs

• Time: O(n) for every trick here. Cyclic placement has a nested loop but at most n swaps in total, because each places one value permanently.
• Space: O(1) beyond the input (the encoded string aside).
• Baseline. Build a new list or a hash set: also O(n) time, but O(n) space. In-place is worth it when the space limit is part of the question, and almost never otherwise.
• Costs. The input is mutated, so these cannot be used when callers share the array; the code is subtle and off-by-one prone, so write the invariant down first. In an interview, say that a copy would be simpler and that you are choosing the in-place version because the constraint asks.

Problems

The home problems span all four tricks plus length-prefix encoding. The "also uses" list shows the same write-index idea inside two-pointer and palindrome problems.

Easy

• 27. Remove Element NeetCode 250
  Copy every element that is not the target forward over a write index; the index at the end is the new length.

Medium

• 31. Next Permutation Grind 169
  Find the rightmost ascent, swap its left value with the smallest larger value to its right, then reverse the descending suffix.
• 189. Rotate Array Grind 169 NeetCode 250
  Reverse the whole array, then reverse the first k and the remaining n-k elements, which rotates in place.
• 271. Encode and Decode Strings Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Prefix each string with its length and a delimiter, so decoding reads lengths and never has to guess where a string ends.

Hard

• 41. First Missing Positive Grind 169 NeetCode 250
  The answer lies in 1..n+1, so place each value v at index v-1 by swapping and then find the first index holding the wrong value.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 26. Remove Duplicates from Sorted Array Easy
• 283. Move Zeroes Easy

Connections

Read and write indices are the simplest two-pointer pattern, which the next page generalises to pointers that move toward each other. Cyclic placement replaces the hash set from the hash maps page when values are bounded, and the counting page's three-way partition is the same family of in-place swaps.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: the partition step of quicksort (chapter 7) is the classic in-place read and write pattern, and chapter 2 gives loop invariants.
• Sedgewick and Wayne, Algorithms: section 2.3 on in-place partitioning, and section 5.1 on key-indexed counting.
• Steven Skiena, The Algorithm Design Manual: the section on generating permutations.
• Donald Knuth, The Art of Computer Programming, volume 4A, section 7.2.1.2: Algorithm L, the next-permutation procedure in lexicographic order.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.