Rearrange Positive and Negative Numbers With Constant Extra Space | Part 1

Solution

There are different approaches to solving the above problem. We will discuss every solution separately.

Approach1(Using Modified Insertion Sort)

As the heading suggests, we will try to solve the problem using Insertion Sort. Don’t know about Insertion Sort? Follow this article to learn about Insertion Sort first.

Idea

Here, we will follow the idea of the Insertion Sort. The simple idea of the Insertion Sort is to transfer one element at a time to its correct position.

The idea is as follows:

• Start from the beginning of the original array, each time you encounter a negative element, transfer the element to its correct position.
   
• Follow the above approach for all negative elements in the array.
   
• When there are no negative elements left, you will get your answer.
   

Visualisation

Let’s now visualise the above idea with an example. Let’s keep the sample input for this case.

Code in C++

#include<bits/stdc++.h>
using namespace std;

void Rearrange(int arr[], int n)
{
    // Traverse the array
    for(int i = 0; i < n ; i++){
        // search for the negative number
        if(arr[i] < 0) {
            int j = i;
            // continue swapping with adjacent element till it reaches the first positive index
            while(j > 0 && arr[j - 1] > 0) {
                swap(arr[j] , arr[j - 1]);
                j--;
            }
        }
    }
}

int main() {

    // given array
    int arr[] = {1 , -2 , 4 , -6, -3, 9};

    // calculate size of the array
    int n = sizeof(arr) / sizeof(arr[0]);

    // call the function
    Rearrange(arr , n);
   
    // print the result
    cout << "Resulting array is: ";
    for(int i = 0 ; i < n; i++) {
        cout << arr[i] <<" ";
    }
}

You can also try this code with Online C++ Compiler

Run Code

Output 

Resulting array is: -2 -6 -3 1 4 9 

Complexity Analysis

If you want to learn more about time and space complexity, you can follow this article, Time and Space Complexity in Algorithms.
Time Complexity: O(n²)

Space Complexity: O(1)

Approach2(Using Modified Partition Property of Quick Sort)

We will try to solve the problem using the Partition Property of the QuickSort Algorithm. If you don’t know about the Partition Property in QuickSort, follow this article, Understanding Quicksort, first.

Idea

Here, we will follow the idea of the Partition Property of QuickSort. 

In Partition Property of Quicksort, we select a pivot in the given array(within the given range). We then compare other elements with the pivot. We divide the array into two parts based on the comparison by keeping the pivot in its appropriate position. The left side of the pivot contains all the smaller elements, and the right side of the pivot contains all the greater elements.

The idea is as follows:

• Select the first positive index of the given array as the pivot.
   
• Scan the array from left to right.
   
• If the current element is negative, swap this element with the pivot.
   
• This may change the relative order of the positive elements(It will happen if more than one positive element appears before the negative element). Consider the below example.
  (N1, N2, P1, P2, P3, N3)
  The pivot element is P1. After scanning the array, we get a negative element N3 at the last index. After swapping it with the pivot element, we get,
  (N1, N2, N3, P2, P3, P1)
  As you can see, the relative order of the positive element got changed.
   
• To keep the order of the positive elements, rotate the array to the right by one position(After swapping, only the index of the pivot element changes, so we need only one right rotation).
   
• We will use Reversal Algorithm for right rotation of an array algorithm for array rotation. 
  
  If you want to know more about array rotation, follow the Array Rotation article.
   

Visualisation

Let’s now visualise the above idea using the sample test case.

Code in C++

#include<bits/stdc++.h>
using namespace std;
 
// reverse the subarray arr[lo , hi]
void Reverse(int arr[] , int lo , int hi) {
    while(lo < hi) {
        int temp = arr[lo];
        arr[lo] = arr[hi];
        arr[hi] = temp;
        lo++;
        hi--;
    }
}
 
// rotate array to one position to the right
// using the Reversal Algorithm
void Rotate(int arr[] , int start_index , int end_index){
     Reverse(arr , start_index + 1, end_index - 1);
     Reverse(arr , start_index, end_index);
}
 
void Rearrange(int arr[], int n)
{
    int pos = 0;
   
    // search for the first positive index(pivot)
    while(pos < n && arr[pos] < 0) {
        pos++;
    }
 
    // start scanning the array after the pivot element
 
    for(int i = pos + 1; i < n ; i++) {
        if(arr[i] < 0) {
            // swap the negative element with the current pivot
            swap(arr[i] , arr[pos]);
 
            // if more than one positive element appear before the next negative number
            // rotate the sub-array[pos + 1 , i] to the right by one
            if(i- pos + 1 > 1)
            Rotate(arr, pos + 1 , i);
 
            pos += 1;
        }
    }
}
 
 
int main() {
 
    // given array
    int arr[] = {1 , -2 , 4 , -6, -3, 9};
 
    // calculate size of the array
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // call the function
    Rearrange(arr , n);
   
    // print the result
    cout << "Resulting array is: ";
    for(int i = 0 ; i < n; i++) {
        cout << arr[i] <<" ";
    }
}

You can also try this code with Online C++ Compiler

Run Code

Output

Resulting array is: -2 -6 -3 1 4 9

Complexity Analysis
 

Time Complexity: O(n²)

Space Complexity: O(1)
 

Follow this link to read about part 2 of the article, Rearrange Positive and Negative Numbers With Constant Extra Space | Part 2.

Frequently Asked Questions

What are the time and space complexity of the mergesort algorithm?

Time complexity: O(nlogn)

Space complexity: O(n)
 

What do you mean by “constant extra space” in a problem?

The space(memory allocation) you have taken to solve the problem doesn’t depend on the input variable.
 

What do you mean by the pivot in data structure?

The pivot element in a data structure is the element that is selected first by an algorithm to solve the problem.
 

What is the role of the pivot element in quick sort?

In Quicksort, we select a pivot in the given array(within the given range). We then compare other elements with the pivot. We divide the array into two parts based on the comparison by keeping the pivot in its appropriate position. The left side of the pivot contains all the smaller elements, and the right side of the pivot contains all the greater elements.

Selecting the pivot element is very important for the quicksort algorithm because the algorithm's run time depends on the pivot selection.

 Also Read - Strong number in c

Conclusion

In this article, we have extensively discussed Rearrange Positive and Negative Numbers With Constant Extra Space.

We started with the basic introduction. We discussed,

• Problem Statement
• Solution 
  • Using Modified Insertion Sort
  • Using Modified Partition Property of Quick Sort Algorithm
     

We hope that this article has helped you enhance your knowledge regarding Rearrange Positive and Negative Numbers With Constant Extra Space. If you want to learn more, follow our articles Find the Minimum Element in a Rotated Sorted Array, Multiple Left Rotation in an Array in O(1), Next Greater and Smaller Element for Every Element in an Array, Understanding Insertion Sort, Understanding Quick Sort. Please upvote this blog to help other ninjas grow.

Recommended Problems -

• Rearrange Array Alternately
• Sum Of Two Arrays
• Merge K Sorted Arrays

Explore our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations and much more.!

Happy Reading!