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

Question

The task:

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

Answer 1

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

To be fair in JS 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)\$ 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)\$ and a complexity of \$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;
}

Answer 2

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.