Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation
3.
Solution
3.1.
Approach1(Using Modified Insertion Sort)
3.1.1.
Idea
3.1.2.
Visualisation
3.1.3.
Code in C++
3.1.4.
Output 
3.1.5.
Complexity Analysis
3.2.
Approach2(Using Modified Partition Property of Quick Sort)
3.2.1.
Idea
3.2.2.
Visualisation
3.2.3.
Code in C++
3.2.4.
Output
3.2.5.
Complexity Analysis 
4.
Frequently Asked Questions
4.1.
What are the time and space complexity of the mergesort algorithm?
4.2.
What do you mean by “constant extra space” in a problem?
4.3.
What do you mean by the pivot in data structure?
4.4.
What is the role of the pivot element in quick sort?
5.
Conclusion
Last Updated: Mar 27, 2024

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

Author Aniket Majhi
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Welcome readers! We hope you are doing well.

Have you ever messed up in a problem where you need to rearrange the elements of the array in place without using any other Data Structure?

Today in this article, we will discuss an interesting problem named rearranging positive and negative numbers with constant extra space.

We will be showing different approaches to solve this problem with a proper flow diagram and explanation.

This blog will help you in dealing with these kinds of problems in the future.

This is the first part of the article. The link to the second part of the article is Rearrange Positive and Negative Numbers With Constant Extra Space | Part 2.

Okay, then, without further ado,  let’s start our discussion.

Problem Statement

You are given an array of positive and negative numbers. You need to rearrange the numbers so that all negative numbers appear before the positive numbers by keeping their order the same as given in the original array without using any extra space.

Example

Let’s understand the above problem with an example.

Input

{1,-2,4,-6,-3,9}

Output

{-2,-6,-3,1,4,9}

Explanation

The given array is {1,-2,4,-6,-3,9}

The rearrangement should follow like below.

As you can see, all the negative numbers come before the positive numbers by keeping their order the same as in the original array.
 

For Negative Numbers: 

    Original Array: Index(-2) < Index(-6) < Index(-3)

    Rearranged Array: Index(-2) < Index(-6) < Index(-3)
 

For Positive Numbers:

    Original Array: Index(1) < Index(4) < Index(9)

    Rearranged Array: Index(1) < Index(4) < Index(9)
 

We hope the problem statement is clear to you now. Let’s move to the solution part.

Also Read - Selection Sort in C and  Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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] <<" ";
    }
}

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(n2)

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] <<" ";
    }
}

Output

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

Complexity Analysis
 

Time Complexity: O(n2)

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 ArrayMultiple Left Rotation in an Array in O(1)Next Greater and Smaller Element for Every Element in an ArrayUnderstanding 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!

Live masterclass