Partition Around Pivot

When To Use

Use this when separating values into groups in-place.

Template

l = 0
r = n - 1
 
while l <= r:
    while l <= r and nums[l] belongs left:
        l++
 
    while l <= r and nums[r] belongs right:
        r--
 
    if l <= r:
        swap nums[l], nums[r]
        l++
        r--

Problems

Sort Colors

Problem: sort 0, 1, and 2 in-place.

Pattern: three-way partition with zero, i, and two.

Applied pseudocode:

zero = 0
i = 0
two = n - 1
 
while i <= two:
    if nums[i] == 0:
        swap nums[i], nums[zero]
        i++
        zero++
    else if nums[i] == 2:
        swap nums[i], nums[two]
        two--
    else:
        i++

Partition Array According to Pivot

Problem: reorder values less than, equal to, and greater than pivot.

Pattern: stable version usually uses extra arrays; in-place version is partitioning.

Kth Largest Element in an Array

Problem: find the kth largest value.

Pattern: quickselect uses partition to discard one side.