Two-Pointer Array Partitioning

Hello! In our previous module, we delved deep into subarray problems, culminating in an advanced application of Kadane's algorithm to solve the maximum circular subarray sum. That work gave you a robust toolkit for handling contiguous subarray challenges.

Today, we pivot to a new module and a different, yet equally fundamental, array manipulation pattern: the two-pointer technique. Our goal is to solve array partitioning problems, which involve grouping elements in-place based on a specific property. We'll master this by tackling the classic "Dutch National Flag" problem. This pattern is a staple in coding interviews, prized for its efficiency and clever use of pointers to avoid extra space.

The Core Idea: In-Place Partitioning

At its heart, partitioning is about rearranging an array so that elements satisfying a certain condition are grouped together. The challenge is to do this in-place, meaning without using a significant amount of extra memory (ideally, O(1) space). The two-pointer technique is the key to achieving this.

Let's start with a simpler, two-part partition problem: Move Zeroes. Given an array of numbers, move all the zeros to the end while maintaining the relative order of the non-zero elements.

A common pitfall is to focus on moving the zeros. A more elegant and powerful insight is to reframe the problem: move all the non-zero elements to the beginning of the array. The zeros will naturally end up at the end as a consequence. This is where two pointers come in. We can use one pointer (left) to mark the boundary of the "processed" non-zero section and another pointer (right) to scan the array.

The logic is as follows:

• The left pointer keeps track of the next position where a non-zero element should be placed.
• The right pointer iterates through the array.
• When nums[right] is non-zero, we swap it with nums[left] and then increment left. This effectively expands our partition of non-zero elements.
• When nums[right] is zero, we do nothing but continue our scan by incrementing right.

This approach ensures all non-zero elements are moved to the front in their original relative order, solving the problem in a single pass.

Three-Way Partitioning: The Dutch National Flag Problem

Now, let's extend this idea to a more complex, three-part partition. This is famously known as the Dutch National Flag problem, proposed by Edsger Dijkstra. The task is to sort an array containing only the numbers 0, 1, and 2. The name comes from the three colors of the Dutch flag (red, white, and blue), which the numbers can be seen to represent.

A straightforward solution would be to count the number of 0s, 1s, and 2s in one pass, and then overwrite the array with the correct number of 0s, then 1s, then 2s in a second pass. This works and has O(N) time complexity, but it requires two passes over the array. The challenge, and the optimal solution, is to do it in a single pass.

To achieve this, we enhance our two-pointer approach into a three-pointer system: low, mid, and high. These pointers divide the array into four conceptual sections:

1. [0 ... low-1]: All 0s.
2. [low ... mid-1]: All 1s.
3. [mid ... high]: The "unprocessed" section we are currently examining.
4. [high+1 ... n-1]: All 2s.

Our goal is to shrink the unprocessed section (mid to high) until it's empty, at which point the array will be sorted. We do this by iterating with the mid pointer and applying three simple rules based on the value of arr[mid].

The logic is beautifully simple:

• If arr[mid] == 0: The 0 belongs in the low section. We swap arr[low] with arr[mid], then increment both low and mid. We increment low because our section of 0s has grown, and we increment mid to move to the next unprocessed element.
• If arr[mid] == 1: The 1 is already in the correct potential spot (the middle section). We simply increment mid to examine the next element. The low pointer does not move.
• If arr[mid] == 2: The 2 belongs at the end. We swap arr[mid] with arr[high], and then only decrement high. We do not increment mid because the element we just swapped into the mid position came from the high end and is itself unprocessed. It needs to be checked in the next iteration.

This process continues until mid crosses high, at which point the entire array is sorted.

The image below provides a step-by-step visual of this process, showing how the pointers move and elements are swapped.

Implementation and Generalization

Now that you understand the logic, let's look at a clean implementation and consider how this pattern can be generalized.

The Dutch National Flag problem is a specific instance of a broader pattern called three-way partitioning. The general problem is to partition an array around a given range [lowVal, highVal] such that all elements less than lowVal come first, followed by elements within the range, and finally elements greater than highVal. The logic is nearly identical, demonstrating the power of recognizing these underlying algorithmic patterns.

Conclusion

In this lesson, you've been introduced to the powerful two-pointer technique for in-place array partitioning. You've seen how a simple problem like "Move Zeroes" can be solved efficiently by reframing the goal, and how this idea can be extended with a third pointer to solve the classic Dutch National Flag problem in a single pass.

Key Takeaways:

• Partitioning is about rearranging an array into groups based on a property, ideally in-place (O(1) space).
• The two-pointer technique is the primary tool for in-place partitioning.
• The Dutch National Flag algorithm uses three pointers (low, mid, high) to sort an array of three unique values in O(N) time and O(1) space.
• The logic revolves around maintaining sorted partitions for 0s and 2s at the ends of the array, while shrinking the central, unsorted partition.

This is our first look at the two-pointer pattern. There are other ways to use two pointers. In our next lesson, we will explore the "opposite-end" variant, where pointers start at the beginning and end of a sorted array and move towards each other to find pairs of elements that satisfy a certain condition.