Partition Array According to Given Pivot - Video Solutions

Problem Overview: You are given an integer array and a pivot value. Reorder the array so that all elements smaller than the pivot appear first, followed by elements equal to the pivot, and then elements greater than the pivot. The relative order of elements in each group must remain the same.

Approach 1: Three Lists Approach (O(n) time, O(n) space)

The most straightforward solution is to simulate the partitioning process using three temporary arrays. Iterate through the input array once and place each element into one of three lists: less, equal, or greater. If the current number is smaller than the pivot, append it to less. If it equals the pivot, append it to equal. Otherwise append it to greater. After processing all elements, concatenate the three lists in order: less + equal + greater. Because elements are appended in the same order they appear, the relative ordering requirement is preserved automatically.

This approach relies on basic array traversal and is easy to reason about. The time complexity is O(n) since each element is processed once. The space complexity is O(n) due to the additional lists. When interviewers prioritize clarity and correctness over memory optimization, this is often the quickest implementation.

Approach 2: In-Place Partitioning (O(n) time, O(1) extra space)

If you want to reduce extra memory usage, you can simulate the same grouping with careful index management. Iterate through the array and build the result directly while tracking boundaries for elements smaller than and equal to the pivot. The idea is similar to the partition logic used in quicksort: maintain positions where the next less-than or equal-to element should be placed while scanning the array once.

Using a two pointers style approach, you move through the array and place elements into their correct region while preserving order. This requires careful shifting or staged placement but avoids allocating new arrays. The algorithm still runs in O(n) time because every element is examined once, while the additional memory stays at O(1).

This approach is more space-efficient and demonstrates a deeper understanding of array manipulation and partitioning strategies. The logic is slightly more complex than the three-list method, so it’s often used when memory constraints matter.

Recommended for interviews: Start with the Three Lists approach. It clearly shows you understand the problem and preserves ordering without tricky edge cases. After that, discuss the in-place optimization. Interviewers like seeing the simple simulation first, followed by a space-optimized partition strategy that still achieves O(n) time.