In-Place Array Compaction with Same-Direction Pointers

In our previous lesson, we explored our first major algorithmic pattern: two pointers moving inward to find a pair in a sorted array. Today, we'll investigate a different but equally powerful variation of this technique. Instead of moving towards each other, the pointers will start together and move in the same direction at different speeds.

This lesson focuses on using this pattern to efficiently compact or deduplicate an array in-place. This is a fundamental skill for problems that require you to "filter" an array without allocating new memory, a common constraint in coding interviews that tests your understanding of array manipulation.

The Core Pattern: Read and Write Pointers

Imagine you have an array and you need to remove certain elements, pushing all the "good" elements to the front. A naive approach might involve creating a new array, but the "in-place" requirement forbids this. Another common mistake is to try and delete elements from the array while iterating over it, which is inefficient and error-prone in most languages, including JavaScript, as it requires shifting all subsequent elements.

The "same-direction" two-pointer technique provides an elegant and efficient solution. We can think of the two pointers as having distinct roles:

1. A read pointer (let's call it i or fast): Its job is to iterate through every single element of the array from beginning to end.
2. A write pointer (let's call it k or slow): Its job is to keep track of the next available position at the beginning of thearray where a "good" element should be placed.

The algorithm works like this: The read pointer scans the array. Whenever it encounters an element we want to keep, we copy that element to the position indicated by the write pointer and then advance the write pointer. If the read pointer finds an element we want to discard, we simply do nothing but advance the read pointer.

This process naturally partitions the array. The elements from index 0 up to (but not including) the write pointer's final position form the compacted result. The elements beyond that point are irrelevant.

Example 1: Moving All Zeros to the End

A classic problem that illustrates this pattern is "Move Zeroes". Given an array like [0, 1, 0, 3, 12], you need to move all the zeros to the end while maintaining the relative order of the non-zero elements, resulting in [1, 3, 12, 0, 0].

A key insight, as explained in the video below, is to reframe the problem. Instead of "moving zeros to the end," think of it as "moving all non-zero elements to the beginning." This is exactly the compaction task we just described.

The following video provides an excellent walkthrough of this reframing and the two-pointer solution.

In this case, the condition for "keeping" an element is simply that it is not zero. The write pointer (L in the video) only advances when a non-zero element is found and placed in its correct spot.

Example 2: Removing All Instances of a Value

Let's apply this pattern to another common problem: removing all occurrences of a specific value from an array in-place. This is LeetCode problem #27, "Remove Element". The logic is identical to "Move Zeroes," but the condition for keeping an element is now element !== val instead of element !== 0.

The following resource provides a great intuitive explanation for this process.

Example 3: Removing Duplicates from a Sorted Array

Now, let's consider a variation where the input array is sorted. The task is to remove duplicates in-place such that each unique element appears only once, while maintaining relative order. This is LeetCode problem #26, "Remove Duplicates from Sorted Array."

Because the array is sorted, all duplicate elements are guaranteed to be adjacent. This simplifies our "keep" condition. We no longer compare an element to a fixed value val. Instead, we keep an element if it's different from the last unique element we kept.

Our write pointer, k, now has a dual role: it not only tells us where to write the next unique element, but nums[k-1] holds the value of the most recently added unique element.

The logic becomes:

1. Initialize a write pointer k at 0.
2. Iterate through the array with a read pointer.
3. For each element nums[i], we keep it if it's the very first element (k === 0) or if it's different from the last element we kept (nums[i] !== nums[k-1]).
4. If we keep it, we copy it to nums[k] and increment k.

The image below illustrates this process perfectly. The left pointer is our write pointer, and the right pointer is our read pointer.

To see this logic explained and implemented, let's turn to another resource.

Key Takeaways

In this lesson, you've learned the "same-direction" or "read/write" two-pointer pattern, a fundamental technique for in-place array modification.

• The Pattern: Use a read pointer to scan the entire array and a write pointer to manage the section of the array containing elements to be kept.
• The Logic: The read pointer moves unconditionally. The write pointer only moves forward after a "kept" element has been copied to its position.
• The Result: This partitions the array into a "kept" section at the beginning and a "discarded" section at the end. The final value of the write pointer gives you the length of the resulting compacted array.
• Versatility: The power of this pattern lies in its flexible "keep" condition, which can be adapted to various problems:
  • Remove Element: Keep if element !== val.
  • Remove Duplicates (Sorted): Keep if element !== last_kept_element.

This pattern is a cornerstone of efficient array manipulation. In our next lesson, we will build on this idea of two pointers moving in the same direction to explore the Sliding Window pattern, which is used to solve a whole different class of problems involving contiguous subarrays.