← Divide & Conquer

Micro-Drill #77 — Partition step (quicksort)

Divide & Conquer Target: 15s

Partition is the heart of quicksort. Same as Lomuto partition — drill until automatic.

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