In-place Array Manipulation Techniques

The Essence of In-Place Algorithms

An in-place algorithm transforms the input data using only a small, constant amount of extra storage. For arrays, this means we rearrange the elements within the array itself, rather than creating a new one. The primary tool for achieving this is the two-pointer technique, which we'll use to swap, shift, and partition elements with precision.

Let's begin with the most straightforward in-place operation: reversing an array.

Array Reversal

To reverse an array in-place, we can use two pointers. One pointer, left, starts at the beginning of the array, and another, right, starts at the end. We swap the elements at these two pointers, then move left one step to the right and right one step to the left. We repeat this process until the pointers meet or cross each other.

This diagram illustrates the two-pointer technique for in-place array reversal. Pointers at the start and end move towards the center, swapping elements as they go.

Here is a concise Python implementation of this logic:

def reverse_array(arr: list, start: int, end: int):
    """Reverses a portion of an array in-place."""
    left, right = start, end
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

# Example usage:
my_array = [1, 2, 3, 4, 5, 6, 7]
reverse_array(my_array, 0, len(my_array) - 1)
print(my_array) # Output: [7, 6, 5, 4, 3, 2, 1]

This simple reverse_array function is a powerful building block, as we are about to see.

Array Rotation: The Three-Reversal Trick

A common interview problem is "Rotate Array" (LeetCode #189), where you need to shift the elements of an array to the right by k steps. For example, rotating [1, 2, 3, 4, 5] by k=2 results in [4, 5, 1, 2, 3].

A simple solution would be to create a new array and place each element arr[i] at its new position (i + k) % n in the new array, where n is the array length. This works, but it requires $O(n)$ extra space. The challenge is to do it in $O(1)$ space.

A clever and highly efficient in-place solution uses our reverse_array function three times. The insight is that a rotation can be achieved by a series of reversals. The following video explains both the straightforward $O(n)$ space approach and this elegant $O(1)$ space solution.

The algorithm for rotating an array of size n by k positions is:

1. Reverse the entire array: [1, 2, 3, 4, 5] -> [5, 4, 3, 2, 1]
2. Reverse the first k elements: [5, 4, 3, 2, 1] -> [4, 5, 3, 2, 1] (with k=2)
3. Reverse the remaining n-k elements: [4, 5, 3, 2, 1] -> [4, 5, 1, 2, 3]

This sequence of operations perfectly achieves the rotation, all within the original array, using only a few variables for pointers.

Array Partitioning

Partitioning is the task of rearranging an array into segments based on some property, often a pivot value. This is another fundamental in-place operation and is the core engine of algorithms like Quicksort.

Two-Way Partitioning: Lomuto's Scheme

The simplest form is two-way partitioning, where we rearrange an array such that all elements less than or equal to a chosen pivot are on one side, and all elements greater than the pivot are on the other.

One of the most well-known methods is the Lomuto partition scheme. It's intuitive and relatively easy to implement.

Lomuto's scheme typically uses the last element as the pivot. It iterates through the array with one pointer j, while another pointer i tracks the boundary for elements smaller than the pivot. If arr[j] is less than or equal to the pivot, it's swapped into the "smaller" section (at index i+1), and i is advanced.

While Lomuto's is easy to understand, the same article also introduces Hoare's partition scheme, which is generally faster but slightly more complex. It uses two pointers that move towards each other from opposite ends of the array. For an interview, knowing that different partitioning strategies exist and understanding the trade-offs (e.g., Lomuto's is simpler, Hoare's is more performant) demonstrates valuable depth of knowledge.

Three-Way Partitioning: The Dutch National Flag Problem

A more advanced and very common interview problem is three-way partitioning. Here, we partition an array into three sections: elements less than a pivot, elements equal to the pivot, and elements greater than the pivot.

The canonical example is the Dutch National Flag problem, proposed by Edsger Dijkstra. Given an array containing only 0s, 1s, and 2s, sort it in-place. For example, [2, 0, 1, 2, 1, 0] should become [0, 0, 1, 1, 2, 2]. This is equivalent to three-way partitioning around a pivot of 1.

The solution uses three pointers: low, mid, and high.

• low: Marks the boundary of the '0's section.
• mid: The current element being processed.
• high: Marks the boundary of the '2's section.

The mid pointer iterates through the array, and we apply one of three rules:

1. If arr[mid] == 0: Swap arr[low] with arr[mid]. Increment both low and mid.
2. If arr[mid] == 1: Do nothing. Just increment mid.
3. If arr[mid] == 2: Swap arr[mid] with arr[high]. Decrement high. Crucially, do not increment mid, because the element just swapped in from the high position needs to be processed.

This process continues until mid surpasses high.

This visualization shows the step-by-step movement of the low, mid, and high pointers to partition an array of 0s, 1s, and 2s in-place.

The following video from NeetCode gives a concise and clear explanation of this powerful algorithm.

For a textual reference of the algorithm, implementation, and complexity analysis, the following resource is also excellent.

Conclusion

In this lesson, you've learned to manipulate arrays directly in memory, a skill that is critical for writing efficient code and passing technical interviews. We've progressed from a simple two-pointer reversal to the clever three-reversal trick for rotation, and finally to the powerful three-pointer partitioning scheme used in the Dutch National Flag problem.

Key Takeaways:

• In-Place Operations: Aim to modify data structures without allocating new ones to achieve $O(1)$ space complexity.
• Pointers are Your Tool: The two-pointer and three-pointer patterns are the primary mechanisms for performing swaps and managing sections within an array.
• Building Blocks: Simple operations like array reversal can be composed into solutions for more complex problems like array rotation.
• Partitioning is Key: Three-way partitioning (Dutch National Flag) is not just a one-off problem; it's a general technique applicable to sorting and selection algorithms.

In our next lesson, we will continue our exploration of core data structures by focusing on strings. You'll find that many of the techniques you learned today, especially two-pointers for in-place manipulation, are directly applicable to solving common string problems like palindrome checks and anagram detection.