How to rearrange an array with both positive and negative items

Given a mixed array of positive and negative numbers, rearrange the array in an alternate fashion, that is, a positive number, and vice versa following every negative number. If the array has more negative numbers than positive numbers (or more positive numbers than negative numbers), then they will be placed at the end of the array. An example of this problem is shown below:

Input array: $[-1, 2, 4, 5, 2, -6, -2]$

Given the input array above, our output array should be as follows:

Output array: $[-1, 2, -6, 4, -2, 5, 2]$

Algorithm

We iterate over the array from left to right and try to find the first out-of-place element.

Out-of-place elements can be of two types:

Negative numbers at the odd index (e.g., 1, 3, 5) are out-of-place
Positive numbers at the even index (e.g., 0, 2, 4) are out-of-place

Note: Index of an array starts from 0.

If we find an out-of-place element, we start to look for the next element of the opposite sign. Then we replace both these elements.

A few example inputs and their respective outputs are shown below:

Example 1

Input array: $[1, -2, 3, 5, 6, -1, -5, -10]$

Output array: $[-2, 1, -1, 3, -5, 5, -10, 6]$

Example 2

Input array: $[-2, -3, -6, -4, -1, 2, 3, 1]$

Output array: $[-2, 2, -3, 3, -6, 1, -4, -1]$

Example 3

Input array: $[-1, -4, -3, 1, 5, 2, 6, 7, 8]$

Output array: $[-1, 1, -4, 5, -3, 2, 6, 7, 8]$

Code example

Let's look at the code below:

#include <iostream>
using namespace std;
int* swap(int* arr, int first, int second) {
  int temp = arr[first];
  arr[first] = arr[second];
  arr[second] = temp;
  return arr;
}
int* rearrange(int* arr, int length) {
  for(int i = 0; i < length; i++) {
    if(i % 2 == 0 && arr[i] >= 0) // even index and positive number, thus out-of-place
    {
      for(int j = i; j < length; j++) {
        if(arr[j] < 0) {
          arr = swap(arr, i, j);
          break;
        }
      }
    }
    else if(i % 2 != 0 && arr[i] < 0) { // odd index and negative number, thus-of-place
      for(int j = i; j < length; j++) {
        if(arr[j] >= 0) {
          arr = swap(arr, i, j);
          break;
        }
      }
    }
  }
  return arr;
}
void printArray(int* arr, int len) {
 for(int i = 0; i < len; i++) {
    cout << arr[i] << " ";
  }
}
int main() {
  // declaring the input array
  // this can be changed to test your own inputs
  int inp_array[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8 };
  int* out_array = NULL;
  int len = sizeof(inp_array)/sizeof(inp_array[0]);
  // printing input and output arrays and callinf the rearrage function
  cout << "Input array:  ";
  printArray(inp_array, len);
  out_array = rearrange(inp_array, len);
  cout << "\nOutput array: ";
  printArray(out_array, len);
  return 0;
}

Algorithm to arrange an array in alternating positive and negative items

Code explanation

The explanation of the code above is as follows:

Lines 4–9: This function swaps the values at the given indexes (first and second).
Line 13: This is the first condition for out-of-place values (positive value at even index).
Lines 15–18: If an out-of-place value is found, then we loop over the remaining values in the array, and if we find a negative value, we swap it with the current value.
Line 23: This is the second condition for out-of-place values (negative value at odd index).
Lines 24–27: If an out-of-place value is found, then we loop over the remaining values in the array, and if we find a positive value, we swap it with the current value.
Lines 41–56: This is the main function, which has all the testing code for our algorithm.

Time complexity

The time complexity of this algorithm is $O(N * N).$ We loop over the array (which takes $O(N)$ ), and if we find an out-of-place value, we swap it with the next value with the opposite sign, which takes $O(N).$ Therefore, the overall time complexity becomes $O(N *N).$

Space complexity

The space complexity of this algorithm is $O(1).$ We swap values in place in the same array, and we do not use any other variables to store any temporary arrays. We use one temporary variable for swapping values.

Free Resources