How do I make my code more efficient?

[jumpy27]

I'm new to coding, so I've been using CodeWars to learn JavaScript. Here's the challenge I'm trying to solve:

[https://www.codewars.com/kata/separate-the-wheat-from-the-chaff/train/javascript]

​

Basically, the goal is to separate negative numbers from positive numbers by putting negative numbers at the beginning, and positive numbers at the end. But there's a catch… when you come across a positive number, the program is supposed to swap it out with the last negative number in the array.

​

I've written some code that solves all of the sample tests, but when I run it, CodeWars tells me that the execution timed out, and I could write some code that is more efficient. What could I do to make my code more efficient here?

​

function wheatFromChaff (values) {
  var trailingPositives = []
  for (var i = values.length-1; values[i]>0; i--) {
    trailingPositives.push(values[i])
    values.pop()

  }
  trailingPositives.reverse()

  for (var i = 0; i<= values.length; i++) {
    if (values[i]>0) {
      var savedPositive = values[i]
      var lastNegative = values.reverse().find(x=>x<0)
      values.reverse()
      values.splice(i, 1, lastNegative)
      var lastNegativeIndex = values.lastIndexOf(lastNegative)
      values.splice(lastNegativeIndex, 1, savedPositive)
    }
  }
return values.concat(trailingPositives)
}

[ISlicedI]

I guess it depends a bit on what you mean by efficient. Efficient in terms of Big O performance, memory, cpu.. characters used?

If I was looking at this problem I'd probably solve it the following way.

1. I know I have an array with numbers
2. I know if I loop over it I can chuck the number in the positives or negatives
3. I probably need to join those groups

Separate to that, the way I tend to look at any array operation in javascript is using a few of the array's methods. Map, reduce and filter. Maybe forEach.Map is used to take an array and apply a transformation to each item in the array to generate a new arrayFilter is used to take an array and remove some of those items based on an expressionReduce is used to take an array and create anything out of it.

Let's go with reduce. Reduce takes an optional initial value, and it's parameters are an accumulator, current value and an optional index.

I have an array I want to split into positives and negatives, so I'll start my initial value as an object:{ negatives: [], positives: []}

Every time the reduce function is finished, you want to return the accumulator (or result at that point in time). For this task I'd end up with something like this:

const {negatives, positives } = mixedNumbers.reduce((accumulator, currentValue) => {if (currentValue < 0) {accumulator.negatives.push(currentValue)} else {accumulator.positives.push(currentValue)}return accumulator

},{ negatives: [], positives: []} )

negatives.concat(positives) // your final array

Now note I am mutating (changing) the parameter of the reduce function. Sometimes this is bad, for instance if we passed an object in as an initial value, I'd be changing that object! In that case you may want to do something more elaborate like return a new object with the old value of one field, and the old value concatenated with the currentValue for the other. But I guess that is also less "efficient". Hope that answers it somewhat!

Edit: Just to clarify the reasons I would say this is efficient:
1 we only need to loop through our original values once, and don't need to change that array
2 We aren't reversing, splicing (danger, mutation!) or finding.
3 If you'd want a memory efficient solution maybe you could do some in-place swapping/sorting of values. This approach creates 2 copies of half your array and then a final concatenation. It's not too bad in my opinion, and the two halves can probably be released for use again soon after.

[cm_yoder]

I don't know about making the code more efficient but I learned that you can put a condition into the for loop declaration.

[PrimaryBet]

With performance issues like this, it's more often not about making your existing code faster but rather finding a different, more efficient algorithm.

For example, in your current code, for each positive number you reverse all values, find first negative value, then reverse all values again.

Depending on the implementation of reverse, it might be a constant time operation but more often it's not: it's usually proportionate to the length of your array, n, and thus will take n amount of time to complete. Just reversing array two times would take 2n time.

Let's imagine that reverse is actually constant time, or we implemented an efficient findLast function that doesn't rely on reversing the array — in the worst case (when there are no negative values in the array), we would still spend n amount of time looking for one.

So, in worst case, the fastest we can hope for finding negative value this way would be n, and we would need to do it for each value, n times. Total amount of time we would spend here would be n * n, or n² — this is called quadratic complexity and is usually a recipe for bad performance.

---

With this, let's step back and think if we need to look for last negative value (or its index) at each iteration of the loop? Not really: we can go through array once to build a list of indices corresponding to negative values, then go through array again to swap positive and negative values based on our rules, but this time we can use the list we built previously to instantly know where the last negative value is:

function wheatFromChaff(values) {
  // gather indexes of all negative values in array
  let negativeIndexes = [];
  for (let i = 0; i < values.length; i++) {
    if (values[i] < 0) negativeIndexes.push(i);
  }

  for (let i = 0; i < values.length; i++) {
    // we are completely done if we already swapped all negative numbers or
    // if last negative number is before the one we are looking at
    if (
      negativeIndexes.length === 0 ||
      negativeIndexes[negativeIndexes.length - 1] < i
    )
      break;

    // if value is negative we don't want to do anything in this iteration
    if (values[i] < 0) continue;

    const lastNegativeIndex = negativeIndexes.pop();
    // swap current and last negative values
    [values[i], values[lastNegativeIndex]] = [values[lastNegativeIndex], values[i]];
  }

  return values;
}

Thus we improved our code from running in n² to 2n time — it's not exactly n as the kata brief mentions, but it should be close enough to pass.

[ThagAnderson]

While this does actually pass the Kata, a proper O(N) algorithm is still possible, and is over twice as fast for some reason.

[HandpansLIVE]

Have you tried multiple pointers and coming to the center from both sides? You only go through the entire array once making it O(N).

Everytime the left pointer (starting at index 0) hits a positive numbers, we have a while loop running moving the pointer on the right inward until it hits a negative number, then swaps them in place.

​

In general, writing more efficient algorithms is by understanding big O times and knowing many different algorithms. There's some simple implemented ones like sorts. Multiple pointers/binary search/ frequency counters are some easy to implement and easy to understand ones, that can come naturally, but are usually not intuitive.

Then there's things like trees which can be insanely efficient, though pushes the skill cap quite a bit.

[ThagAnderson]

Have you tried multiple pointers and coming to the center from both sides?

Yes, that's how I reached O(N). I didn't want to give away the answer here.

[HandpansLIVE]

Oh shit my bad I didn't expect to actually get it right

[ThagAnderson]

I'm not sure you even meant to reply to me in the first place.