Partition Array According to Given Pivot

Partition Array According to Given Pivot

What is this problem about?

The Partition Array According to Given Pivot problem asks you to rearrange an array such that all elements less than pivot come first, then elements equal to pivot, then elements greater than pivot. The relative order within each group must be preserved. This coding problem is a stable three-way partition. The array, two pointers, and simulation interview pattern is demonstrated.

Why is this asked in interviews?

Apple, Microsoft, Amazon, Google, and Bloomberg ask this to test stable partitioning — where original relative order within groups must be maintained. This is distinct from Dutch National Flag (which doesn't require stability). The simple approach uses three separate lists.

Algorithmic pattern used

Three-group collection. Maintain three lists: less, equal, greater. Traverse the array once: if element < pivot, append to less; if == pivot, append to equal; if > pivot, append to greater. Concatenate: less + equal + greater. This is O(n) time and O(n) space.

Example explanation

nums=[9,12,5,10,14,3,10], pivot=10.

• less=[9,5,3], equal=[10,10], greater=[12,14]. Result: [9,5,3,10,10,12,14].

Common mistakes candidates make

• Using in-place Dutch National Flag (doesn't preserve relative order).
• Sorting after partitioning (breaks relative order).
• Confusing stability with just ordering (groups must maintain input sequence).
• Using extra comparisons instead of three-group approach.

Interview preparation tip

Stable partition problems require an extra O(n) space solution (three lists) because in-place partitioning (Dutch National Flag) doesn't preserve relative order. Distinguish between: (1) Dutch National Flag (in-place, O(1) space, unstable), (2) stable 3-way partition (O(n) space, order-preserving). In interviews, clarify whether stability is required before choosing the approach.