In-Place Array Modification

Welcome to your next lesson. In our previous session, we explored the prefix sum technique, a classic space-time trade-off where we used O(N) extra space to answer range-sum queries in O(1) time. Today, we're flipping that coin to look at problems where the goal is to use no extra space at all, or more precisely, O(1) auxiliary space.

This lesson is designed to help you master the learning outcome: Modify an array in place while preserving the portion that has already been processed. This is a fundamental skill for solving a large class of array-based interview problems efficiently. We'll uncover a powerful pattern that allows you to overwrite parts of an array in a single pass without losing track of your progress. This technique is not just about saving memory; it's about developing a structured way to think about array transformations.

The Core Idea: Partitioning In-Place

Many array problems ask you to "remove" or "rearrange" elements under certain conditions, but with the critical constraint that you must do it "in-place," meaning you modify the original array without creating a new one. Your extensive experience with JavaScript's mutable arrays gives you a solid foundation here, but we'll formalize the underlying algorithmic pattern.

The key insight is to think of the array as being divided into two partitions during the process:

1. A "processed" or "kept" section at the beginning of the array, which contains the elements that satisfy our condition and are in their final positions.
2. An "unprocessed" section containing the remaining elements that we still need to examine.

We can manage these partitions using two pointers, often called a "slow" pointer and a "fast" pointer, that move in the same direction.

• The slow pointer (let's call it write_idx) marks the boundary of the "processed" section. It tells us where to place the next element we want to keep.
• The fast pointer (let's call it read_idx) scans through the array, examining each element.

As the read_idx finds elements worth keeping, it copies them to the write_idx position, and write_idx advances. This effectively overwrites the "unwanted" elements while compactly building the desired result at the start of the array.

This resource provides a great "bookshelf" analogy for this process. Instead of shifting all the books, you simply pick the ones you want and place them at the beginning of the shelf.

Pattern in Action 1: Remove Element

Let's apply this pattern to a classic problem: LeetCode 27. Remove Element.

• Problem: Given an array nums and a value val, remove all instances of val in-place and return the new length. The order of the elements that are not val can be changed.

For example, if nums = [3, 2, 2, 3] and val = 3, the goal is to modify nums so its first two elements are 2, 2. The function should return 2.

Here, the "processed" section consists of elements not equal to val.

• Our write_idx will start at 0.
• Our read_idx will iterate through the entire array.
• For each element nums[read_idx], if it is not equal to val, we consider it "kept." We copy it to nums[write_idx] and then increment write_idx.
• If nums[read_idx] is equal to val, we simply ignore it and continue, letting read_idx advance. The "unwanted" element will eventually be overwritten.

The following resource provides a superb, detailed walkthrough of this exact process.

Pattern in Action 2: Remove Duplicates from a Sorted Array

Now let's consider a variation: LeetCode 26. Remove Duplicates from Sorted Array.

• Problem: Given a sorted array nums, remove the duplicates in-place such that each unique element appears only once. Return the new length.

Example: nums = [1, 1, 2], result should be nums = [1, 2, _] and return 2.

The logic is very similar, but the condition for "keeping" an element changes. Since the array is sorted, we know that duplicates will be adjacent. An element is a "new" unique element if it's different from the last unique element we kept.

• write_idx (let's call it slow) can again track the end of our unique-elements-so-far section.
• read_idx (let's call it fast) scans ahead.
• The first element is always unique, so we can conceptually start with slow at index 0.
• We then iterate with fast starting from index 1. If nums[fast] is different from nums[slow], it's a new unique element. We increment slow first, then copy nums[fast] to this new position nums[slow].

The image below illustrates a moment in this process, where pointer i (our slow pointer) is at the last unique element found, and j (our fast pointer) has found a new unique element.

The following video provides an excellent visual demonstration of this algorithm.

Generalizing the Pattern: A Reusable Template

By now, you've likely noticed the recurring structure. We can abstract this into a general template. Recognizing this pattern is a huge step toward overcoming "algo phobia"—it turns a seemingly novel problem into a familiar one.

The resource below formalizes this pattern as the "Fast-Slow Pointer Technique" and provides a generic template.

Here's the template adapted for TypeScript. It forms the backbone of our in-place modification strategy.

function inPlaceModification(nums: any[]): number {
    if (nums.length === 0) {
        return 0;
    }

    let write_idx = 0; // Pointer for the 'processed' partition

    for (let read_idx = 0; read_idx < nums.length; read_idx++) {
        // The core logic: decide if the element at read_idx should be kept
        if (/* condition to keep nums[read_idx] is true */) {
            nums[write_idx] = nums[read_idx];
            write_idx++; // Expand the 'processed' partition
        }
    }

    return write_idx; // The new length of the valid part of the array
}

Pattern in Action 3: Move Zeroes

Let's tackle one more problem to solidify the pattern: LeetCode 283. Move Zeroes.

• Problem: Given an array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. This must be done in-place.

Example: nums = [0, 1, 0, 3, 12] should become [1, 3, 12, 0, 0].

At first, this might seem different. But think about the problem differently: moving zeroes to the end is the same as moving all non-zero elements to the beginning, while maintaining their relative order. This reframing makes it a perfect fit for our template!

The condition to "keep" an element is simply nums[read_idx] !== 0.

After the loop in our template finishes, all non-zero elements will be at the start of the array, from index 0 to write_idx - 1. The write_idx now points to the first position where a zero should be. We can simply loop from write_idx to the end of the array and fill the remaining spots with zeroes.

This video masterfully explains this rephrasing and solution.

Conclusion

In this lesson, you've learned a powerful and versatile pattern for in-place array modification. This technique is fundamental and appears in many variations.

Key Takeaways:

• In-Place Mindset: Instead of deleting or creating new arrays, think about overwriting elements by partitioning the array into a "kept" section and an "unprocessed" section.
• The Fast-Slow Pointer Pattern: Use a write pointer (slow) to track the end of the "kept" section and a read pointer (fast) to scan the array.
• Adaptable Condition: The core of solving a new problem is identifying the specific if condition that determines whether an element should be kept.
• Complexity: This pattern typically yields solutions with O(N) time complexity (a single pass) and O(1) space complexity (no extra arrays).

This pattern is a cornerstone of array manipulation. As you practice, you'll start to recognize it instantly whenever a problem mentions "in-place modification" and "O(1) space."

In our next lesson, we will move from one-dimensional arrays to two-dimensional grids. We'll learn how to traverse a matrix without omitting or revisiting cells at its boundaries, extending our systematic approach to traversal into a new dimension.