Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 3

Two-Pointer Partitioning for Arrays

Recommended resources

Hello and welcome back!

In our previous lessons, we've seen how two-pointers can be used to find pairs in sorted arrays (2Sum) or optimize search in geometric problems (Container with Most Water). Today, we'll explore another powerful application of this pattern: partitioning an array.

Our focus will be on the famous Dutch National Flag problem, a classic interview question that perfectly demonstrates how to partition an array into three distinct sections in a single, efficient pass. Mastering this technique is a significant step toward tackling medium-level array problems often seen in FAANG interviews.

By the end of this lesson, you will be able to implement the three-pointer approach to solve partitioning problems like LeetCode's "Sort Colors" in optimal time and space.

1. The Problem: Sorting Three Unique Elements

The problem, often presented as "Sort Colors" (LeetCode 75), is simple to state but has an elegant solution.

Problem: You are given an array nums containing only the integers 0, 1, and 2. Sort this array in-place so that all 0s come first, followed by all 1s, and finally all 2s.

A simple approach would be to count the occurrences of 0s, 1s, and 2s and then overwrite the array. However, this requires two passes over the data. The challenge, and what interviewers want to see, is a single-pass, constant-space solution.

This video provides an excellent introduction to the problem and its constraints.

Sort Colors (LeetCode 75) | Dutch National Flag Problem | Full Solution with Visuals and Animations

Let's watch this segment from a video by Nikhil Lohia that clearly defines the 'Sort Colors' problem and explains why naive approaches like using extra arrays or standard library sorts don't meet the typical interview constraints.

Watch from the beginning (00:37) until 05:24. This will set up the problem statement and rule out less optimal solutions, paving the way for the efficient algorithm we're about to learn.

2. The Core Idea: Three-Way Partitioning

The efficient solution is named the Dutch National Flag algorithm after the three colors of the Dutch flag (red, white, and blue), which correspond to our numbers 0, 1, and 2. The algorithm works by partitioning the array into four conceptual sections during the sorting process:

Dutch National Flag Algorithm Visualization
This image illustrates the core invariant of the algorithm. The array is divided into a section of 0s, a section of 1s, an unknown middle section that we are processing, and a section of 2s at the end.

To manage these sections, we use three pointers:

  • low: Points to the boundary right after the last known 0. Everything to the left of low is a 0.
  • mid: The "current" pointer that iterates through the array, processing unknown elements.
  • high: Points to the boundary just before the first known 2. Everything to the right of high is a 2.

Our goal is to shrink the "unknown" region (mid to high) until it disappears, at which point the array will be sorted.

3. The Algorithm in Action

The mid pointer scans the array. Depending on the value it encounters (nums[mid]), we perform one of three actions. This video provides a fantastic animated walkthrough of the entire process.

Sort Colors (LeetCode 75) | Dutch National Flag Problem | Full Solution with Visuals and Animations

This is the heart of the lesson. The following clip from Nikhil Lohia's video visually demonstrates the movement of the low, mid, and high pointers and the swaps that occur. Pay close attention to how each of the three cases (0, 1, or 2) is handled.

Please watch from 05:24 to 12:01. This covers the Dutch National Flag analogy, the step-by-step execution of the algorithm with visuals, and a summary of the rules.

After watching the video, let's solidify the rules of the algorithm. The loop continues as long as mid <= high:

  1. If nums[mid] is 0:

    • This 0 belongs in the low section.
    • We swap nums[low] and nums[mid].
    • We then increment both low and mid. We can increment mid because we know the element we just swapped into the mid position came from the low section, which must be a 1 (since all 0s are already to the left of low).

  2. If nums[mid] is 1:

    • This 1 is already in its correct, "middle" partition.
    • We do nothing but increment mid to examine the next element.

  3. If nums[mid] is 2:

    • This 2 belongs in the high section.
    • We swap nums[mid] and nums[high].
    • We then decrement high. Crucially, we do not increment mid. Why? The element we just swapped from the high position is unknown. It could be a 0, 1, or another 2. We need to process this new nums[mid] in the next iteration of the loop.

This last point is subtle but vital for correctness and is a great detail to explain in an interview.

Test your understanding!

Consider the array nums = [2, 0, 1].
Initial state: low = 0, mid = 0, high = 2.

  1. nums[mid] is 2. What happens? What are the new pointer values and the new array state?
  2. After that, what is the next value of nums[mid] and what is the next action?
Show answer

  1. Step 1: nums[mid] (which is nums[0]) is 2.

    • Swap nums[mid] with nums[high]. The array becomes [1, 0, 2].
    • Decrement high.
    • Pointers are now: low = 0, mid = 0, high = 1. The array is [1, 0, 2].

  2. Step 2: nums[mid] (which is nums[0]) is now 1.

    • This is a 1, so we just increment mid.
    • Pointers are now: low = 0, mid = 1, high = 1. The array is [1, 0, 2].

  3. Step 3: nums[mid] (which is nums[1]) is 0.

    • Swap nums[low] with nums[mid]. The array becomes [0, 1, 2].
    • Increment low and mid.
    • Pointers are now: low = 1, mid = 2, high = 1.
    • The loop condition mid <= high is now false, so the algorithm terminates. The array is correctly sorted: [0, 1, 2].

4. Implementation and Complexity

Now that we understand the logic, let's look at a clean implementation. Your background in Node.js makes you familiar with JavaScript, but the logic is identical in Python, Java, or C++, which are commonly used in interviews.

Dutch National Flag Algorithm Interview Questions

This article from interm.ai provides a concise summary and clear code implementations. It's a great reference to see the algorithm written out.

First, review the 'Processing Rules' under 'Algorithm Mechanics' to reinforce the logic. Then, examine the 'Python Implementation' to see how these rules translate directly to code. Finally, read the 'Complexity Analysis' section to confirm your understanding of its performance.

As the article confirms:

  • Time Complexity: O(n) because the mid pointer traverses the array from beginning to end, and each element is swapped at most once. This is a single-pass algorithm.
  • Space Complexity: O(1) because we only use a few variables (low, mid, high) to perform the sort in-place. No extra data structures are needed.

This combination of linear time and constant space is what makes the Dutch National Flag algorithm the optimal solution for this problem.

Conclusion

Today, we added a crucial partitioning pattern to your two-pointer toolkit. The Dutch National Flag algorithm is not just a solution to a specific LeetCode problem; it's a template for any problem requiring three-way partitioning. Its underlying principle is also used to optimize sorting algorithms like Quicksort when dealing with many duplicate elements.

Key Takeaways:

  • The Dutch National Flag algorithm solves the "Sort Colors" problem in O(n) time and O(1) space.
  • It uses three pointers (low, mid, high) to maintain an invariant that partitions the array into four sections: 0s, 1s, unknown, and 2s.
  • The core logic is a loop that processes the element at mid and performs a swap based on whether it's a 0 or a 2.
  • A critical detail is not to advance the mid pointer when swapping with high, as the newly acquired element at mid needs to be processed.

Preview of the Next Lesson:
We've now covered two fundamental variations of the two-pointer technique. In our next lesson, we'll pivot to another essential pattern for array and string problems: the Sliding Window. We will start by learning how to use a variable-size sliding window to find subarrays or substrings that satisfy a given condition. See you then