Rearrange positive and negative number in array with only one variable – Java

Krrishnaaaa

Problem statement: We have a list of positive and negative numbers in a random order. We have to rearrange the items so that negative numbers appear on the left side of the list and positive numbers on the right side of the list.

Constraint: We can use only one variable. We are not allowed to create second array.

Solution: To solve this problem we can traverse the array (arr) from the beginning to the end and check for following conditions. While doing so we have to keep one index at the end (posIdx) to keep track of positive numbers.

  1. If current element is negative then move to next item.
  2. If current element is positive and arr[posIdx] is negative then swap. (Here we need one extra variable)
  3. If current element is positive and arr[posIdx] is positive too then decrement posIdx by one and continue
  4. If posIdx is less than or equals to the current index then break the loop.

To print the array we are using this method.

private void printArray(int[] arr) {
    for (int a : arr) {
        System.out.print(" " + a);
    }
    System.out.println();
}

To rearrange the elements by following the above mentioned rules 

private void rearrangeNumbers(int[] arr) {
    System.out.print("\noriginal:  ");
    printArray(arr);
    int length = arr.length;
    int posIdx = length - 1;
    for (int i = 0; i < length; ) {
        if (arr[i] < 0) {
            i++;
        } else {
            if (arr[posIdx] < 0) {
                int temp = arr[posIdx];
                arr[posIdx--] = arr[i];
                arr[i] = temp;
            } else {
                posIdx--;
            }
        }
        if (posIdx <= i) {
            break;
        }
    }
    System.out.print("processed: ");
    printArray(arr);
}

Related