In-Place Array Manipulation Techniques

The In-Place Constraint

An "in-place" algorithm transforms the input data without allocating significant extra memory for its intermediate results. The space complexity must be $O(1)$, meaning the memory used doesn't scale with the size of the input. For arrays, this typically involves rearranging elements by swapping them, overwriting them, or using a few variables as pointers or temporary storage. This constraint challenges you to be creative and efficient with the memory you already have.

Problem 1: Move Zeroes

Let's start with a common interview problem: given an integer array, move all the zeroes to the end of it while maintaining the relative order of the non-zero elements.

For example, [0, 1, 0, 3, 12] should become [1, 3, 12, 0, 0].

A simple approach would be to create a new array, copy all non-zero elements into it, and then fill the remaining spots with zeroes. However, this would require $O(n)$ extra space for the new array, violating the in-place requirement.

The optimal, in-place solution uses the two-pointer pattern. The idea is to partition the array into two conceptual parts: non-zero elements at the beginning and the rest of the array (which will eventually be zeroes) at the end.

We can use one pointer, let's call it nonZeroIndex, to mark the boundary of the non-zero section. This pointer indicates the position where the next non-zero element should be placed. We then iterate through the array with a second pointer, currentIndex.

When currentIndex finds a non-zero element, we place it at the nonZeroIndex position and advance nonZeroIndex. This effectively compacts all non-zero elements to the front of the array in their original order.

The following resource provides a superb, in-depth explanation of this technique, complete with a walkthrough and a clean Java implementation.

To reinforce this concept with a quick visual, you can watch this short segment from a video on the two-pointer pattern.

By using this two-pointer strategy, we solve the problem in $O(n)$ time, as we traverse the array once, and with $O(1)$ space, satisfying all constraints.

Problem 2: Rotate Array

Our second problem is another classic: rotate an array to the right by k steps. A right rotation moves the last element to the front and shifts everything else one position to the right.

For example, rotating [1, 2, 3, 4, 5, 6] by k = 2 steps results in [5, 6, 1, 2, 3, 4].

A Naive but Inefficient Approach

A straightforward idea is to perform the rotation one step at a time, and repeat this k times. For each step, you'd save the last element, shift all other elements one position to the right, and then place the saved element at the front. This would work, but what's the time complexity? Each rotation takes $O(n)$ time, and we do this k times, leading to an overall complexity of $O(n\cdot k)$. If k is large (e.g., on the order of n), this becomes $O(n^2)$, which is too slow for most interview contexts.

The following video explains this naive method clearly. Understanding it is useful for discussing trade-offs with an interviewer.

The Efficient Reversal Algorithm

Fortunately, there is a much more elegant and efficient ($O(n)$) in-place solution that uses three array reversals. This is a clever trick that is very valuable to know for interviews.

The algorithm works in three steps:

1. Reverse the entire array. This places the last k elements (the ones that should be at the front) at the beginning, but in reversed order.
2. Reverse the first k elements. This corrects the order of the elements that have now moved to the front.
3. Reverse the remaining n-k elements. This corrects the order of the elements that have shifted to the back.

Let's trace this with nums = [1, 2, 3, 4, 5, 6, 7] and k = 3.

1. Original: [1, 2, 3, 4, 5, 6, 7]
2. After reversing the whole array: [7, 6, 5, 4, 3, 2, 1]
3. After reversing the first k=3 elements: [5, 6, 7, 4, 3, 2, 1]
4. After reversing the last n-k=4 elements: [5, 6, 7, 1, 2, 3, 4]

The result is the correctly rotated array. This algorithm accomplishes the rotation in $O(n)$ time, since each element is part of at most two reversals, and uses $O(1)$ space.

The following article provides a complete walkthrough of this powerful technique.

Conclusion

In this lesson, you've mastered two fundamental in-place array manipulation patterns. These problems highlight how constraints on memory force us to devise clever, efficient algorithms by creatively using the structure of the data itself.

Key takeaways:

• In-Place Algorithms: Operate with $O(1)$ space complexity, modifying the input directly, often through swapping.
• Move Zeroes: Solved efficiently in a single pass using a two-pointer approach to partition the array into non-zero and zero sections.
• Rotate Array: The naive $O(n\cdot k)$ approach is inefficient. The optimal in-place solution uses the three-reversal algorithm to achieve an $O(n)$ time complexity.

This lesson marks the end of our first module on complexity and core array patterns. You've built a solid foundation in analyzing algorithms and applying powerful techniques like two-pointers, sliding windows, prefix sums, and in-place manipulation.

In our next lesson, we will begin a new module and dive into Linked Lists. We'll move from the world of contiguous memory (arrays) to a structure based on nodes and pointers, opening up a new set of problems and algorithmic strategies.