Move all negative elements to end

This problem is the easier version of the problem we solved earlier in this series. So let's start by looking at the simple approach first.

Simple Approach

The logic for this one is quite simple, you need to create two new arrays one with all the negative numbers of the array and then one with all the positive numbers. Then you can return a concatenation of the two arrays.

function simple_sort_neg_pos(arr) {
  let neg_arr = arr.filter((e) => e < 0);
  let pos_arr = arr.filter((e) => e >= 0);

  return [...neg_arr, ...pos_arr];
}

simple_sort_neg_pos([4, -3, 5, 0, 9, -9, 1, 2, 5]);
-> [-3, -9, 5, 0, 9, 4, 1, 2, 5]

This solution requires O(n) space. Let's bring it down to O(1)!

Two Pointer Approach

Since we sorted an array of 0s, 1s and 2s last time, for the sake of consistency, I will use similar initial pointers in this code. We will have two pointers

• i representing the end of negative numbers

• j representing the end of positive numbers and it will also be our iterator

We will traverse the array until j reaches the last index. And we will handle the negative and positive numbers accordingly as we encounter them.

If the current element at j is positive, we simply move to the next element. But if it is negative, then we move the i pointer to the next element(increment it by one) and swap the elements at arr[i] and arr[j]. And then we move j to the next element.

function sort_neg_pos(arr) {
  let i = -1;
  let j = 0;
  while (j < arr.length) {
    if (arr[j] < 0) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
      j++;
    } else {
      j++;
    }
  }

  return arr;
}

sort_neg_pos([4, -3, 5, 0, 9, -9, 1, 2, 5]);
-> [-3, -9, 5, 0, 9, 4, 1, 2, 5]

Try dry running this code as it might not seem quite intuitive at first glance. Also last time we sorted an array of 0s, 1s and 2s where I explained my thought process with diagrams. You can read it here.

Next time on DSA 450 Series, we find the union and intersection of two sorted arrays.