Three-way partitioning around a range

Medium

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.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

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;
}