32. Three-Way Partitioning of an Array Around a Given Value

Given an array and a pivot value, rearrange the array into three groups in this order: elements less than the pivot, elements equal to the pivot, then elements greater than the pivot - preserving each group's original relative order. Print the result.

Input: The first line contains n and the pivot value, space-separated. The second line contains n space-separated integers. Output: Print the rearranged array (elements less than the pivot, then equal, then greater), space-separated on one line.

1 <= n <= 10^5

This is the 'Dutch National Flag' problem in disguise - a classic three-way partitioning pattern that also has a genuinely in-place, single-pass variant (using three pointers) if preserving strict relative order isn't required, worth knowing about as a follow-up.

Rearrange an array into three clear sections: everything smaller than a given pivot value, then everything equal to it, then everything larger - keeping each section's original relative order. Brute force: Sort the entire array around the pivot using a general-purpose sort - this technically produces a valid three-way grouping, but a full sort (O(n log n)) does far more work than necessary for what's really just a three-bucket classification. Optimised: Since you only need three GROUPS (not a fully sorted order within each group beyond preserving original relative order), a single linear classification pass - bucketing each element by comparison to the pivot - achieves the goal in O(n), without the overhead of a full comparison-based sort.

Achieve the same stable three-way grouping without allocating separate auxiliary lists, using the block-swap/rotation technique behind library stable-partition implementations: recursively partition the array in place by rotating adjacent blocks of 'wrong-group' elements past each other, which preserves relative order within each group without copying elements into new storage. This trades a small increase in time complexity (an extra logarithmic factor from the rotations) for dropping the auxiliary array entirely, which is worthwhile when memory is the binding constraint for arrays up to size 10^5. Time: O(n log n) Space: O(1)

Make a single left-to-right pass over the array, appending each element to one of three separate lists depending on whether it's less than, equal to, or greater than the pivot. Because each list is built purely by appending in original scan order, the relative order within each group is automatically preserved. Concatenating the three lists (less, then equal, then greater) gives the final answer in one linear pass, at the cost of allocating extra arrays proportional to the input size. Time: O(n) Space: O(n)

Repeatedly scan the array and, whenever an element is found sitting before another element that should logically come earlier (i.e. a 'greater than pivot' element sitting before a 'less than pivot' element, or similar out-of-group ordering), shift it into place one step at a time via adjacent swaps, similar to how insertion sort moves elements while preserving the relative order of equal-priority items. This is slow because elements may need to move many positions one swap at a time, but it never uses more than a constant amount of extra memory. Time: O(n^2) Space: O(1)

1. Walk through the array once, classifying each element as less-than, equal-to, or greater-than the pivot. 2. Collect each classification into its own separate list, preserving original order within each. 3. Concatenate the three lists in order: less-than, then equal-to, then greater-than.

Time: O(n) - one single pass through the array to classify every element. Space: O(n), for the three temporary bucket lists before concatenation.

n = 1 (a single element, trivially in one group); no elements equal to the pivot, or none less than / greater than it; and n = 10^5 (largest, confirming the single-pass classify approach is O(n)).

This is directly related to the 'partition' step at the heart of quicksort - recognizing the connection (quicksort's partition step is essentially a two-way version of this three-way split) is a nice signal of connecting concepts across the DSA curriculum.