Separate The Wheat From The Chaff - CodeWars Challenge

Question

Introduction

The problem is explained on Link to challenge for best instructions

As far as I understand, the idea is to swap elements on the left side of an array with elements from the right side of an array if the element on the left side is greater than 0.

I.e. [2, -4, 6, -6] => [-6, -4, 6, 2].

Positives on the left side have to get swapped with their corresponding "out of place" opposite on the right side. So, unfortunately we can't use

array = array.sort((a, b) => a - b);

In the end, there should be only negatives numbers on the left side and positives on the right side. If the array has an odd length, then one "side" will be one (or more) elements larger, depending on whether or not there are more positives or negatives in the original array.

I.e. [8, 10, -6, -7, 9, 5] => [-7, -6, 10, 8, 9, 5]

Approach

To solve this, I created a pretty lengthy algorithm that splits the array into halfs, and keeps track of "out of place" (positive) elements on the left side and "out of place" (negative) elements on the right side, to use for swapping:

function wheatFromChaff (values) {
  
  //IF ORIGINAL VALUES LENGTH IS EVEN
  if (values.length % 2 === 0) {

    let left = values.slice(0, values.length / 2);
    let right = values.slice(values.length / 2);
    
    let outOfPlaceLeft = left.filter((element) => element > 0);
    let outOfPlaceRight = right.filter((element) => element < 0);

    //replace positive "out of place" left elements with negative "out of place" right elements
    for (let i = 0; i < left.length; i++) {
      if (left[i] > 0) {
        left.splice(i, 1, outOfPlaceRight.pop());
      }
    }
      
    //push remaining "out of place" negative right elements to the left
    while (outOfPlaceRight.length) {
      let first = outOfPlaceRight.shift();
      left.push(first);
    }
    
    //filter out any negatives on the right
    right = right.filter((element) => element > 0).concat(outOfPlaceLeft);

    //concat the remaining positives and return
    return left.concat(right);
  }

  //IF ORIGINAL VALUES LENGTH IS ODD
  if (values.length % 2 !== 0) {

    let left2 = values.slice(0, Math.floor(values.length / 2));
    let right2 = values.slice(Math.ceil(values.length / 2));
    let middle = values[Math.floor(values.length/2)];
    
    let outOfPlaceLeft2 = left2.filter((element) => element > 0);
    let outOfPlaceRight2 = right2.filter((element) => element < 0);

    //replace "out of place", positive left elements
    for (let j = 0; j < left2.length; j++) {
      //if out of there are out of place elements on the right
      if (outOfPlaceRight2.length) {
        if (left2[j] > 0) {
          left2.splice(j, 1, outOfPlaceRight2.pop());
        }
      }
      //if out of place elements on the right are empty
      if (!outOfPlaceRight2.length && middle < 0) {

        if (left2[j] > 0) {
          left2.splice(j, 1, middle);
        }
      }
    }
    
    //filter out negatives on the right
    right2 = right2.filter((element) => element > 0);
    
    //unshift remaining "out of place" positive left elements to the right
    while (outOfPlaceLeft2.length) {
      let first = outOfPlaceLeft2.shift();
      right2.unshift(first);
    }
    if (middle > 0) {
      right2.unshift(middle);
    }
    if (middle < 0) {
      left2.push(middle);
    }
    return left2.concat(right2);
  }
}
console.log(wheatFromChaff([2, -6, -4, 1, -8, -2]));

Sometimes the previous approach works, but it gives me an error on Codewars:

AssertionError [ERR_ASSERTION]: [ -10, 7 ] deepEqual [ -10, -3, 7 ]

Do you see any flaws with my logic? Any suggestions for a better strategy?

Answer 1

I have solved this using two "pointers" one starting on the head of the array, and the other starting at the tail of the array. The idea is, on every iteration, to increment the head or decrement the tail iteratively until you found a positive number on the head pointer and a negative number at the tail pointer. When this condition is satisfied, then you have to do a swap on the positions of the elements and continue. Finally, you have to stop the loop when the head pointer is greater than the tail pointer.

function wheatFromChaff(values)
{
    let res = [];
    let head = 0, tail = values.length - 1;

    while (head <= tail)
    {
       if (values[head] < 0)
       {
           res[head] = values[head++];
       }
       else if (values[tail] > 0)
       {
           res[tail] = values[tail--];
       }
       else
       {
           res[tail] = values[head];
           res[head++] = values[tail--];
       }
    }

    return res;
}

console.log(wheatFromChaff([2, -4, 6, -6]));
console.log(wheatFromChaff([8, 10, -6, -7, 9]));

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

This approach passed all test mentioned on that link:

Time: 894ms Passed: 5 Failed: 0

But maybe there is a better solution.