Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
1.1.
Problem Statement
1.2.
Sample Examples 
2.
Solution Approach 
2.1.
Steps of algorithm
2.2.
Implementation in C++
2.3.
Implementation in Python
2.3.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What are the differences between array and strings?
3.2.
Which sorting algorithm is used when we sort using STL? 
3.3.
What are the differences between array and object?   
3.4.
Can we pass a negative number as the size of the array? 
4.
Conclusion 
Last Updated: Mar 27, 2024

Rearrange positive and negative using the inbuilt sort function

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

Introduction 

This article will look at the Rearrangement of positive and negative numbers and the order of numbers that need to be maintained. Array-based questions are the most popular and vital in coding interviews and programming competitions. Let's understand the problem statement

Problem Statement

The problem states that we are given an array of size N, containing both positive and negative numbers, and we need to rearrange the array such that all negative integers come before positive integers and the order in which they come should remain the same. 

Let's Discuss the sample example to understand the problem better. 

Sample Examples 

Input:

arr[] = {-1,2,1,3,-1,-2,-3}

 

Output:

{-1, -1, -2, -3, 2, 1, 3}

 

Explanation: In the above example, we have rearranged the numbers so that all negative comes before positive, and the order of elements is the same.  

 

Input: 

arr[] = {-1, 1, -2, 3, -2, 2, 4, 9, 8}

 

Output:

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

 

Explanation: In the above example, we have rearranged the numbers so that all negative comes before positive, and the order of elements is the same.   

Solution Approach 

The idea is simple; we will use the C++ inbuilt function and a comparator function to modify the sorting function according to our requirements—a few cases needed to be handled in the comparator function. We will have two arguments in the comparator function, namely num1 and num2, and the index will be i and j, and i>j. If the comparator function returns true, then the swap will be done. Otherwise, nothing happens.    

Conditions:

num1 index i > num2 index j, The index of the first argument in comparator function is higher. 

 

Condition 1: if(num1>0 && num2>0) || (num1<0 && num2<0) || (num1>0 && num2<0) 

Return false, 

This condition states that if elements are either positive or negative, don't swap them, and also if the element at jth index is negative and the element at ith index is positive, don't swap them because we need to put negative elements at the front. 

 

Condition 2: if(num1<0 && num2>0) return true 

This condition states that if num1<0 and num2>0, the higher index element is negative; therefore, swapping is required, hence return true. 

Now we also need to handle the cases if the element is 0. We need to put 0 in between negative and positive elements. 

 

Condition 3: if(num1==0 && num2<0 || num1>0 && num2==0) return false; 

This condition states that if element on left of 0 is negative, or element right to 0 is positive then we don’t need to swap any element. 

 

Condition 4: if(num1<0 && num2==0 || num1<0 && num2==0) return true; 

This condition states that if element on right of 0 is negative and element on left of 0 is positive then swapping is needed. 

Steps of algorithm

  • Call the comparator function 
  • In the comparator function, we have 2 arguments (int num1, int num2), and apply the above four conditions as explained 
  • Finally, the array we received will be the rearranged array. 

Implementation in C++

// C++ program to rearrange postive and negative elements
#include<bits/stdc++.h>
using namespace std;
static bool cmp(int num1, int num2){
    // condition 1
    if((num1>0 && num2>0) || (num1<0 && num2<0) || (num1>0 && num2<0)) return false;

    // condition 2
    if(num1<0 && num2>0) return true;

    // condition 3
    if(num1==0 && num2<0 || num1>0 && num2==0) return false;

    // condition 4
    if(num1==0 && num2>0 || num1<0 && num2==0) return true;

}
int main(){
    vector<int>arr = {-1,2,1,3, 0, 0, -1,-2,-3};
    int n = arr.size();
    
    // printing the array before rearrangement
    cout << "Array before the rearrangement: ";
    for(int i=0;i<n;i++) cout << arr[i] << " ";
    cout << endl;
    
    // calling the sort function
    sort(arr.begin(), arr.end(), cmp);
    cout << "Array after the rearrangement: ";
    
    // Rearrange  Array 
    for(int i=0;i<n;i++) cout << arr[i] << " ";
    cout << endl;

}

 

Output: 

Array before the rearrangement: -1 2 1 3 0 0 -1 -2 -3
Array after the rearrangement: -1 -1 -2 -3 0 0 2 1 3

Implementation in Python

# python program to rearrange positive and negative elements
from operator import ne
import functools


def compare(num1, num2):

    if (num1 > 0 and num2 > 0) or (num1 < 0 and num2 < 0) or (num1 > 0 and num2 < 0):
        return 0

        # condition 2
    if (num1 < 0 and num2 > 0):
        return -1

        # condition 3
    if (num1 == 0 and num2 < 0) or (num1 > 0 and num2 == 0):
        return 0

        # condition 4
    if (num1 == 0 and num2 > 0) or (num1 < 0 and num2 == 0):
        return 1


arr = [-1, 2, 1, 3, -1, -2, -3]
# printing the array before rearrangement
print("Array before the rearrangement: ")
print(arr)

# intiliazing the temp variable to bring negative elements at the front

arr = sorted(arr, key=functools.cmp_to_key(compare))


# printing the array before rearrangement
print("Array after the rearrangement: ")
# rearrange array 
print(arr)

 

Output:

Array before the rearrangement: 
[-1, 2, 1, 3, -1, -2, -3]
Array after the rearrangement: 
[-1, -1, -2, -3, 2, 1, 3]

 

Complexity Analysis

Time Complexity: O(NLogN)

We are doing sorting on the basis of customized conditions, so time complexity is O(NlogN). 

Space Complexity: O(1)

We are not using any temporary array, so therefore space complexity is O(1).  

Also see, Morris Traversal for Inorder and  Rabin Karp 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

Frequently Asked Questions

What are the differences between array and strings?

Array is a data structure that stores the same set of elements, while strings store the set of characters. 

Which sorting algorithm is used when we sort using STL? 

The sorting algorithm used in STL sort() is IntroSort. Introsort is a hybrid sorting algorithm that uses three sorting algorithms to minimize the running time. These algorithms are quicksort, Heapsort, and Insertion Sort.

What are the differences between array and object?   

Major differences between array and objects are:

  •  An array creates a collection of data and keeps it in a single variable, whereas an object represents an entity with characteristics (called a property). We can access, alter, and delete items from objects using brackets and dots, whereas we can access and modify items in arrays using a range of built-in methods and zero-based indexing. Various loops (e.g., for, for...in, for...of, forEach()) can traverse across object properties and array entries.
     
  • On the heap, all Java objects are dynamically allocated. Unlike C++, where objects can be allocated to Heap or Stack in memory. When we call the new() method in C++, the object is allocated on the heap unless it is global or static, in which case it is allocated on Stack.

Can we pass a negative number as the size of the array? 

ArrayIndexOutOfBounds is a runtime exception that happens when a program tries to access an array with an incorrect index, such as one that is greater than the array's size or a negative index.

Conclusion 

In this article, we discussed a very interesting problem, in which we have to rearrange such that all negative numbers come before positive numbers and the order of elements needs to remain the same. We hope you understand the problem and solution properly. Now you can do more similar questions. you may check out our Interview Preparation Course to level up your programming journey and get placed at your dream company. 

Recommended Problems -

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview undle and interview experiences for placement preparations.

Thank you for reading. 

Until then, Keep Learning and Keep Coding.

Previous article
Segregate 0s and 1s in an Array
Next article
Rearrange the array such that the even index elements are smaller and the odd index elements are greater
Live masterclass