3
\$\begingroup\$

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));
\$\endgroup\$
5
\$\begingroup\$

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)\$ 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;
}
\$\endgroup\$
  • \$\begingroup\$ How long did it take you to solve it (from reading the first word to typing the last code)? \$\endgroup\$ – thadeuszlay Mar 21 at 5:38
  • \$\begingroup\$ @thadeuszlay Not long for the basics 10-15 min, worked for your example, but tested some other arguments and it did not work, All up about an hour. I needed to add visualization so I could see the bugs in action. Had to add step \$\endgroup\$ – Blindman67 Mar 21 at 5:50
  • \$\begingroup\$ What do you mean by you had to „add visualization“? You mean had to add the step variable or are you speaking of a visualization tool? \$\endgroup\$ – thadeuszlay Mar 21 at 6:18
  • \$\begingroup\$ @thadeuszlay I have my own custom editor (ace,js at the core) that lets me debug and edit while extracting info to a canvas but needs extra code to direct what is being visualized.. step was the fix that it helped me find. \$\endgroup\$ – Blindman67 Mar 21 at 6:29
5
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.