Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Partition
DSA

Partition

Learn partitioning techniques for rearranging arrays around conditions, pivots, or selected values.

Partitioning rearranges elements into groups in-place using pointers.

The most famous version:

Dutch National Flag → sort 0s, 1s and 2s in one pass.

Focus on recognizing:

Grouping/classification without full sorting → Partition

Core Template: Dutch National Flag

Three pointers carve the array into regions — 0s | 1s | unknown | 2s:

public void sortColors(int[] nums) {
    int low = 0;
    int mid = 0;
    int high = nums.length - 1;

    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums, low++, mid++);
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(nums, mid, high--);
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}
def sort_colors(nums):
    low = 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], nums[high] = nums[high], nums[mid]
            high -= 1
void sortColors(vector<int>& nums) {
    int low = 0, mid = 0;
    int high = (int)nums.size() - 1;

    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums[low++], nums[mid++]);
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(nums[mid], nums[high--]);
        }
    }
}
function sortColors(nums) {
  const swap = (i, j) => ([nums[i], nums[j]] = [nums[j], nums[i]]);
  let low = 0,
    mid = 0,
    high = nums.length - 1;

  while (mid <= high) {
    if (nums[mid] === 0) {
      swap(low++, mid++);
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      swap(mid, high--);
    }
  }
}

nums[mid] == 0 → send left · == 1 → keep · == 2 → send right. The swapped-in value from high is re-examined; the one from low never is.

Maintain regions, not comparisons — each element lands in its zone exactly once.

Pattern 1: Pivot Partition (QuickSort Step)

Watch [2,0,2,1,1,0] get sorted in a single pass as low/mid/high carve their regions. Press ▶ to animate.

Dutch National Flag (One Pass vs Counting)

Sort an array containing only 0, 1, and 2. The elegant one-pass solution is Dutch National Flag (three pointers); the easy alternative is counting sort (tally then overwrite in two passes).

Array [2,0,2,1,1,0]. low=mid=0, high=5. mid sees 2 → swap with high (2↔0) and high--, but DO NOT advance mid (the swapped-in value is unexamined). 0 → swap into the 0-zone and advance both. 1 → just mid++. Watch the three zones meet: [0,0,1,1,1,2] in one pass. The key trap is rechecking mid after a 2-swap.

ARRAY VISUALIZER
Steps –
2
0
0
1
2
2
1
3
1
4
0
5
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        low = 0, mid = 0, high = n - 1
                      
                        2
                        while mid <= high:
                      
                        3
                          if nums[mid] == 0:
                      
                        4
                            swap(low, mid); low++; mid++   // 0 → front
                      
                        5
                          elif nums[mid] == 1:
                      
                        6
                            mid++                          // 1 stays middle
                      
                        7
                          else:
                      
                        8
                            swap(mid, high); high--        // 2 → back; recheck mid!

Two-way split around a pivot — DNF with one fewer region:

public int partition(int[] nums, int pivot) {
    int i = 0;

    for (int j = 0; j < nums.length; j++) {
        if (nums[j] < pivot) {
            swap(nums, i, j);
            i++;
        }
    }

    return i;
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}
def partition(nums, pivot):
    i = 0

    for j in range(len(nums)):
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1

    return i
int partition(vector<int>& nums, int pivot) {
    int i = 0;

    for (int j = 0; j < (int)nums.size(); j++) {
        if (nums[j] < pivot) {
            swap(nums[i], nums[j]);
            i++;
        }
    }

    return i;
}
function partition(nums, pivot) {
  let i = 0;

  for (let j = 0; j < nums.length; j++) {
    if (nums[j] < pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }

  return i;
}

Same skeleton handles even/odd or positive/negative segregation — only the condition changes.

Pattern 2: QuickSelect Partition

Each partition discards half the array — kth smallest without full sort.

Quickselect (Kth Smallest)

Find the k-th smallest element by partitioning and discarding one side each round.

Pick a pivot, partition so smaller elements sit left. If the pivot index equals the target, return it; otherwise recurse only into the side containing the target. Each round discards half the array on average → O(n).

ARRAY VISUALIZER
Steps –
9
0
3
1
7
2
1
3
8
4
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        target = k-1; lo = 0; hi = n-1
                      
                        2
                        p = partition(lo, hi)
                      
                        3
                        if p == target: return nums[p]
                      
                        4
                        if p < target: lo = p+1 else hi = p-1

Pivot fixed at the end; returns its final index — the backbone of QuickSort and Kth-element selection:

public int partitionKth(int[] nums, int left, int right) {
    int pivot = nums[right];
    int i = left;

    for (int j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            swap(nums, i, j);
            i++;
        }
    }

    swap(nums, i, right);
    return i;
}
def partition_kth(nums, left, right):
    pivot = nums[right]
    i = left

    for j in range(left, right):
        if nums[j] <= pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1

    nums[i], nums[right] = nums[right], nums[i]
    return i
int partitionKth(vector<int>& nums, int left, int right) {
    int pivot = nums[right];
    int i = left;

    for (int j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            swap(nums[i], nums[j]);
            i++;
        }
    }

    swap(nums[i], nums[right]);
    return i;
}
function partitionKth(nums, left, right) {
  const pivot = nums[right];
  let i = left;

  for (let j = left; j < right; j++) {
    if (nums[j] <= pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }

  [nums[i], nums[right]] = [nums[right], nums[i]];
  return i;
}

After this runs, nums[i] is in its final sorted position — recurse into one side for QuickSelect.

Common Mistakes

Advancing mid after swapping with high.

The value swapped in from high is unexamined — decrement high but do NOT advance mid.

Losing region invariants.

Every pointer has a meaning (<low are 0s, >high are 2s). If you can’t state what each region holds, the loop is wrong.

Using DNF for two-category problems.

Pivot partition is simpler — reach for three pointers only when there are truly three classes.

Complexity

PatternTimeSpace
DNFO(n)O(1)
PivotO(n)O(1)
QuickSelectO(n) averageO(1)

My Private Notes

Notes are auto-saved locally to this device.