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^{2})
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 subarray[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^{2})
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 
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!