# Given a pivot x, and a list lst, partition the list into three parts

Posted on

Problem

Given a pivot x, and a list lst, partition the list into three parts.

The first part contains all elements in lst that are less than x The
second part contains all elements in lst that are equal to x The third
part contains all elements in lst that are larger than x Ordering
within a part can be arbitrary.

For example, given x = 10 and lst = [9, 12, 3, 5, 14, 10, 10], one
partition may be [9, 3, 5, 10, 10, 12, 14].

My solution:

const createPartitionOf = (lst, pivot) => {
const lessLst = lst.filter(x => x < pivot);
const equalLst = lst.filter(x => x === pivot);
const largerLst = lst.filter(x => x > pivot);
return [...lessLst, ...equalLst, ...largerLst];
};

console.log(createPartitionOf([9, 12, 3, 5, 14, 10, 10], 10));


My solution2:

const createPartitionOf2 = (lst, pivot) => {
const lessLst = [];
const equalLst = [];
const largerLst = [];
for (let i = 0; i < lst.length; i++) {
if (lst[i] < pivot) {
lessLst.push(lst[i]);
} else if (lst[i] > pivot) {
largerLst.push(lst[i]);
} else {
equalLst.push(lst[i]);
}
}
return [...lessLst, ...equalLst, ...largerLst];
};

console.log(createPartitionOf2([9, 12, 3, 5, 14, 10, 10], 10));


Solution

These problems are always looking to test. It seamed way to straight forward until I realized the clue.

To be fair in JS a there is no such thing as a list which helps understand the problem.

## This is a storage problem

The Question I think is implying that the array be partitioned in place “partition the list”. The aim is to keep storage complexity down. With a side benefit of reduced complexity?

The clue that gives the solution away is the part “Ordering within a part can be arbitrary”

## Strategy

If we think of the problem as separating high and low values (above and below the pivot) you can step the array and swap high values with the current value using an index that moves down.

To deal with the middle values (which you do not know the position of until you know how many there are) you use a consuming index. That is an index made of two parts, the first part is the current index that will hold the current value, the second part is an offset (ahead on the index) that is the location that we get the current value from.

When the consuming index meets the top index we fill the remaining items with the pivot value.

## Solution $$O(1) O(1) O(1) storage$$

Well that is the gist of it. The solution turned out a little more complicated (it was a hard one) But it maintains a storage complexity of $$O(1)$$

$O\left(1\right)$

$O(1)$ and a complexity of $$O(n)$$

$O\left(n\right)$

$O(n)$ (was hoped it could be log(n) but edge cases made it impossible for my mind)

This is not the best possible solution, I am sure there are some shortcuts and unnecessary code in this.

function partition(arr, pivot) {
var i, temp, top = arr.length - 1, mid = 0, step = true;
for (i = 0; i <= top - mid; i++) {
if (mid && step) { arr[i] = arr[i + mid] }
step = true;
if (arr[i] > pivot) {
if (arr[top] === pivot) {
arr[top--] = arr[i];
arr[i] = arr[i + (++mid)];
} else {
temp = arr[i];
arr[i] = arr[top];
arr[top--] = temp;
step = false;
}
i--;
} else if(arr[i] === pivot) {
mid++;
i--;
}
}
while (mid--) { arr[i++] = pivot }
return arr;
}



In your first solution you are traversing the list 3 times, whereas in the second solution only once. Given the functional-tag, I’d say you’re after the reduce function:

const flatten = (acc, x) => acc.concat(x)

const pivotPartition = (pivot, ary) => {
const toOrdered = (triplet, n) => {
let [less, equal, greater] = triplet

switch(true) {
case n < pivot: less.push(n); break
case n > pivot: greater.push(n); break
default: equal.push(n)
}

return triplet
}

return ary.reduce(toOrdered, [[], [], []]).reduce(flatten)
}


If you want to sort the subarrays as well, then the whole thing is just a ary.sort((a, b) => a - b), although as it is mutating the list, it isn’t a functional solution.

Consider 2 Pointers low and high are keep moving towards center direction ultimately x == value will be centered

        int x = 10;
Integer[] intList = new Integer[] {9, 12, 3, 5, 14, 17, 10, 10};
int pointlow=0, pointhigh = intList.length-1;
Integer arr[] = new Integer[intList.length];

for(int i=0; i<= intList.length-1; i++) {
if(intList[i] < x) {
arr[pointlow] = intList[i];
pointlow++;
}
else {
arr[pointhigh] = intList[i];
pointhigh--;
}
}
System.out.println(Arrays.asList(arr));
`