Array Layout Presets
Pointer Tracking
Algorithm Loop
The 3-Pointer Trick
LOW tracks the boundary for 0s.
HIGH tracks the boundary for 2s.
MID scans the array from left to right.
mid > high, sorting is mathematically complete in
$O(N)$ time.
Live Console Log
Dutch National Flag Algorithm
The Dutch National Flag Algorithm (proposed by Edsger W. Dijkstra) is a classic computer science problem. The goal is to sort an array containing exclusively three distinct values (e.g., 0, 1, and 2) in linear time $O(N)$ and constant space $O(1)$ in a single pass.
Low Pointer (0s)
Everything to the left of low is guaranteed to be
0. Points to the location where the next 0 should be placed.
Mid Pointer (1s)
The current element being evaluated. Elements between
low and mid-1 are guaranteed to be 1.
High Pointer (2s)
Everything to the right of high is guaranteed to
be 2. Points to the location where the next 2 should go.
Algorithm Implementation
class Solution {
public void sortColors(int[] nums) {
int low = 0;
int mid = 0;
int high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) {
// Swap mid and low, then increment both
swap(nums, low, mid);
low++;
mid++;
} else if (nums[mid] == 1) {
// 1 is in the correct middle section, just move mid
mid++;
} else {
// nums[mid] == 2
// Swap mid and high, decrement high. Do NOT increment mid yet!
swap(nums, mid, high);
high--;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
void sortColors(vector<int>& nums) {
int low = 0;
int mid = 0;
int high = nums.size() - 1;
while (mid <= high) {
if (nums[mid] == 0) {
swap(nums[low], nums[mid]);
low++;
mid++;
} else if (nums[mid] == 1) {
mid++;
} else {
// nums[mid] == 2
swap(nums[mid], nums[high]);
high--;
}
}
}
};class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
low = 0
mid = 0
high = len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
# nums[mid] == 2
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1