← Pointer Manipulation

Micro-Drill #9 — Partition around pivot (Lomuto)

Pointer Manipulation Target: 15s

Lomuto partition is the core of quicksort and quickselect. Know it cold for kth-element problems.

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

Type it from memory. Go.

Practice Problems

• 215. Kth Largest Element in an Array
• 912. Sort an Array

Related Coding Drills

• Drill #31 — Quick sort (Lomuto partition) Medium
• Drill #149 — Partition Labels Medium