Three-way partitioning around a range
Problem
Given an array and a range [low, high], rearrange the array in place into three groups: elements smaller than low first, then elements within [low, high], then elements greater than high. Order inside each group does not matter. Use a single pass.
Example 1
Input: arr = [1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32], low = 14, high = 20 Output: [1, 5, 4, 2, 1, 3, 14, 20, 20, 98, 87, 32, 54]
Also asked as: Three way partitioning of an array around a given value
Test cases
No automated tests for this problem yet. Use the examples above to check your output.
This problem has no automated tests. Run executes your code and shows what it logs.
View solutionHide solution1 approach
1. Dutch-flag variant
Time O(n)Space O(1)
Elements < lowVal go left of `low`, elements > highVal go right of `high`, the rest stay in the middle.
function threeWayPartition(a, lowVal, highVal) { let low = 0, mid = 0, high = a.length - 1; while (mid <= high) { if (a[mid] < lowVal) { [a[low], a[mid]] = [a[mid], a[low]]; low++; mid++; } else if (a[mid] > highVal) { [a[mid], a[high]] = [a[high], a[mid]]; high--; } else mid++; } return a;}