Array Partitioning with Pointers

Hello! In our previous lessons, we've focused on using two pointers to define a "sliding window"—a contiguous subarray whose properties we analyze. You've become adept at expanding and contracting this window to solve problems like finding the minimum substring that meets certain criteria.

Today, we're going to pivot to a different, equally powerful application of the two-pointer pattern: partitioning. Instead of just observing a subarray, we'll use pointers to actively rearrange an array's elements in-place. The goal is to group elements into distinct regions based on a chosen condition. This is a fundamental technique you'll encounter frequently, both as a standalone problem and as a building block for more complex algorithms like Quicksort.

By the end of this lesson, you will be able to partition an array into distinct regions using several different pointer strategies, and you'll understand which strategy to apply based on the problem's constraints.

Two-Way Partitioning: Inward-Moving Pointers

Let's start with the most straightforward type of partitioning. Imagine you're given an array of numbers and asked to move all the even numbers to the left side and all the odd numbers to the right side. The relative order of the even numbers among themselves doesn't matter, and the same goes for the odd numbers.

This is a classic partitioning problem. The core idea is to establish two "regions" in the array: an "even" region on the left and an "odd" region on the right. We can do this efficiently with two pointers starting at opposite ends of the array.

• A left pointer starts at the beginning. Its job is to find the first odd number, which is "misplaced" in the even region.
• A right pointer starts at the end. Its job is to find the first even number, which is "misplaced" in the odd region.

Once both pointers have found a misplaced element, we simply swap them. This places both numbers in their correct respective regions. We then continue moving the pointers inward until they meet or cross, at which point the array is fully partitioned.

The following resource from Algo.monster provides an excellent explanation of this logic for the "Sort Array By Parity" problem.

The partitioning logic you've just reviewed is a cornerstone of many algorithms. For example, the famous Quicksort algorithm uses this exact mechanism to partition an array around a "pivot" value.

Here is the TypeScript implementation from the resource you read. It cleanly translates the logic of advancing pointers for "correctly placed" elements and swapping "misplaced" ones.

function sortArrayByParity(nums: number[]): number[] {
    let leftIndex: number = 0;
    let rightIndex: number = nums.length - 1;

    while (leftIndex < rightIndex) {
        // If left element is even, it's in the right place. Move on.
        if (nums[leftIndex] % 2 === 0) {
            leftIndex++;
        } 
        // If right element is odd, it's in the right place. Move on.
        else if (nums[rightIndex] % 2 === 1) {
            rightIndex--;
        } 
        // Otherwise, left is odd and right is even. They are misplaced. Swap them.
        else {
            [nums[leftIndex], nums[rightIndex]] = [nums[rightIndex], nums[leftIndex]];
            leftIndex++;
            rightIndex--;
        }
    }
    return nums;
}

This pattern is highly efficient, running in $O(n)$ time with $O(1)$ space, as it only requires a single pass and modifies the array in-place.

Partitioning While Maintaining Relative Order

Now, let's add a constraint. What if you need to partition an array, but the relative order of the elements within one of the partitions must be preserved?

Consider the "Move Zeroes" problem: given an array, move all 0s to the end while maintaining the relative order of the non-zero elements.

For [0, 1, 0, 3, 12], the result must be [1, 3, 12, 0, 0]. Note that 1, 3, and 12 appear in the same order as they did in the original array. The inward-moving pointer approach from before won't work here, because swapping an element from the end (like 12) with a zero at the beginning would break the relative order.

We need a different pointer strategy. A common solution uses two pointers that move in the same direction:

1. A write pointer (let's call it k) marks the end of the "processed non-zero" region. It indicates the next position where a non-zero element should be placed.
2. A read pointer (let's call it i) iterates through the entire array from left to right.

As the read pointer i scans the array, if it encounters a non-zero element, it swaps that element with the one at the write pointer's position k, and then k is incremented. This effectively collects all non-zero elements at the beginning of the array, in the order they were found.

This article from Algo.monster provides a fantastic analogy and a clear walkthrough.

As you saw, the key is to focus on placing the "desired" elements (the non-zeros) correctly. The "undesired" elements (the zeros) naturally end up in the remaining space. This single-pass swap-based approach is both elegant and efficient.

Three-Way Partitioning: The Dutch National Flag Problem

We've partitioned an array into two regions. Can we do it for three?

Absolutely. This is the basis of the famous Dutch National Flag problem, first proposed by Edsger Dijkstra. Given an array containing only the numbers 0, 1, and 2, sort it in-place. The final array should have all the 0s first, then all the 1s, and finally all the 2s.

This requires partitioning the array into three distinct regions:
[region of 0s | region of 1s | region of unknowns | region of 2s]

To manage these regions, we use three pointers:

• low: Marks the boundary after the 0s region.
• mid: The current element under consideration. It scans through the "unknown" region.
• high: Marks the boundary before the 2s region.

The algorithm iterates as long as mid <= high:

1. If nums[mid] is a 0: It belongs in the low region. We swap nums[mid] with nums[low] and increment both low and mid.
2. If nums[mid] is a 1: It's in the correct middle region (for now). We don't need to move it, so we just increment mid to examine the next element.
3. If nums[mid] is a 2: It belongs in the high region. We swap nums[mid] with nums[high] and decrement high. Crucially, we do not increment mid because the new element at nums[mid] came from the high boundary and we haven't processed it yet.

This video provides an excellent animated explanation of this algorithm.

The animated GIF below provides a quick summary of the process you just watched. The three pointers methodically shrink the "unknown" region from both sides until the array is fully sorted.

Conclusion

In this lesson, you've added several powerful partitioning strategies to your algorithmic toolkit. You've moved beyond using pointers to simply define a window and are now using them to efficiently reorganize arrays in-place.

Key Takeaways:

• Partitioning is the process of rearranging an array into distinct regions based on a condition.
• For two-way partitioning where relative order is unimportant (e.g., evens/odds), use inward-moving pointers from opposite ends of the array.
• When relative order must be preserved, use same-direction pointers (a "read" pointer and a "write" pointer) to collect elements into their new positions.
• For three-way partitioning (e.g., sorting 0s, 1s, and 2s), the Dutch National Flag algorithm with low, mid, and high pointers is the standard, efficient approach.

The crucial skill is to identify the problem's constraints—how many partitions are needed, and does relative order matter?—to select the correct pointer strategy.

In our next and final lesson of this module, we will synthesize what you've learned. You'll practice how to choose between hashing, two pointers, and a sliding window when presented with a problem, solidifying your pattern-recognition abilities.