Quicksort Partition Pattern: Lomuto, Hoare & Dutch National Flag

Partitioning is one of the most fundamental algorithmic operations you will encounter in coding interviews. At its core, partitioning rearranges elements in an array around a pivot value — elements less than the pivot go to the left, and elements greater go to the right. This single operation powers quicksort, quickselect, and dozens of array rearrangement problems on LeetCode.

What makes the quicksort partition pattern so valuable for interviews is that it appears in disguise across many problem types. Sort Colors (#75), Kth Largest Element (#215), and Move Zeroes (#283) all rely on the same partitioning logic. Once you internalize the partition step, these problems become straightforward applications of a technique you already know.

In this guide, you will learn three partition variants — Lomuto, Hoare, and the Dutch National Flag — and understand exactly when to use each one. We will connect each technique to real LeetCode problems so you can practice immediately.

The Lomuto partition scheme is the simplest and most commonly taught version of the quicksort partition algorithm. It uses a single boundary pointer that tracks where the "less than pivot" region ends. You scan left to right, and whenever you find an element smaller than the pivot, you swap it to the boundary and advance the boundary forward.

Here is how Lomuto partition works step by step. Choose the last element as the pivot. Initialize a boundary index i at the start of the array. Iterate through each element with index j. If the element at j is less than the pivot, swap it with the element at i, then increment i. After the loop, swap the pivot into position i. Now everything left of i is smaller than the pivot, and everything right of i is larger.

The Lomuto scheme performs more swaps than Hoare on average, but its simplicity makes it the go-to choice for interviews. You maintain exactly one invariant — the boundary between small and large elements — which means fewer chances for off-by-one errors under time pressure.

The Hoare partition scheme uses two pointers starting from opposite ends of the array. The left pointer moves right until it finds an element greater than or equal to the pivot. The right pointer moves left until it finds an element less than or equal to the pivot. When both pointers have stopped, you swap the two elements and continue until the pointers cross.

Hoare partition is more efficient than Lomuto in practice because it performs roughly three times fewer swaps on average. The two-pointer approach naturally handles the case where many elements are equal to the pivot, distributing them across both sides rather than piling them on one side as Lomuto does.

However, Hoare partition is trickier to implement correctly. The pivot does not necessarily end up in its final sorted position after one pass, which means the recursive calls must include the boundary element. Off-by-one errors are common, especially around the loop termination condition. For this reason, many interview coaches recommend Lomuto unless you have practiced Hoare extensively.

The Dutch National Flag algorithm, designed by Edsger Dijkstra, extends partitioning to three regions: elements less than the pivot, equal to the pivot, and greater than the pivot. This three-way partition is essential when dealing with arrays that contain many duplicate values, and it is the direct solution to Sort Colors (#75), one of the most frequently asked medium-level interview problems.

The algorithm maintains three pointers: low, mid, and high. The low pointer marks the boundary of the "less than" region, mid is the current scanning pointer, and high marks the boundary of the "greater than" region. As mid scans forward, elements are swapped into the correct region. When mid crosses high, the partition is complete.

Three-way partitioning also improves quicksort performance on arrays with many duplicates. Standard two-way partition degrades to O(n squared) when all elements are identical, because every partition places only one element. The Dutch National Flag groups all equal elements in the middle, so the recursive calls skip them entirely.

Quickselect is the most important application of the partition algorithm beyond sorting. It finds the Kth smallest (or largest) element in an unsorted array in average O(n) time — no need to sort the entire array. The key insight is that after one partition, the pivot is in its final sorted position. If that position is K, you are done. If not, you only recurse into the half that contains K.

LeetCode problem #215 (Kth Largest Element in an Array) is the canonical quickselect problem and appears frequently in interviews at Google, Meta, and Amazon. The naive approach sorts in O(n log n), but quickselect solves it in average O(n) by discarding half the array at each step — similar to binary search but on an unsorted array.

To implement quickselect, run Lomuto partition on the array. If the pivot index equals K, return the pivot. If K is less than the pivot index, recurse on the left subarray. If K is greater, recurse on the right subarray. With random pivot selection, the expected number of comparisons is 2n, making it linear on average.

Partition problems have a reputation for being tricky to implement correctly, and interviewers know this. The most common mistake is choosing the first or last element as the pivot without randomization. On sorted or nearly sorted input — which interviewers love to test — this produces the worst-case O(n squared) behavior because every partition is maximally unbalanced.

Off-by-one boundary errors are the second most frequent issue. In Lomuto partition, forgetting to swap the pivot into its final position after the loop leaves the array incorrectly partitioned. In Hoare partition, using the wrong comparison operator (less-than vs. less-than-or-equal) can cause infinite loops when duplicate elements are present.

Not handling equal elements is another subtle bug. If your partition places all elements equal to the pivot on one side, arrays with many duplicates degrade to O(n squared) even with good pivot selection. The Dutch National Flag three-way partition solves this by grouping equal elements in the middle, but if you are using Lomuto or Hoare, at least ensure equal elements can appear on either side of the partition.

Start your partition practice with Sort Colors (#75), the purest application of the Dutch National Flag algorithm. This problem asks you to sort an array containing only 0s, 1s, and 2s in a single pass with O(1) space. It is a direct implementation of three-way partitioning and will solidify your understanding of the low, mid, and high pointer technique.

Next, tackle Kth Largest Element in an Array (#215) using quickselect. This problem tests whether you can apply the partition step selectively — partitioning once and then recursing only into the relevant half. Practice both the recursive and iterative versions, and always randomize your pivot.

Once those two problems feel comfortable, expand to Move Zeroes (#283), which is a simplified Lomuto partition where the pivot is zero. Then try Partition Labels (#763) and Sort Array By Parity (#905) to see how the partition concept extends beyond numeric pivots. With YeetCode flashcards, you can drill the pattern recognition for each variant through spaced repetition, ensuring the partition step becomes automatic when you see these problems in a real interview.