Rearrange Array in negative numbers, zero and then positive numbers order
Given an arr[ ] of size N, containing positive, negative integers and one zero. The task is to rearrange the array in such a way that all negative numbers are on the left of 0 and all positive numbers are on the right.
Note: It is not mandatory to maintain the order of the numbers. If there are multiple possible answers, print any of them.
Examples:
Input: arr[] = {1, 0, -2, 3, 4, -5, -7, 9, -3}
Output: -2 -3 -5 -7 0 1 9 3 4
Explanation: The negative numbers are -2, -5, -7 and -3.Input: arr[] = {-10, 5, -2, 0, -4, 5, 17, -9, -13, 11}
Output: -10 -2 -4 -13 -9 0 17 5 5 11
Naive approach: Create an array of size N and push negative numbers from starting and positive numbers from the end. Also, fill the single remaining place with 0.
Time complexity: O(N)
Auxiliary Space: O(N)
Efficient approach: The idea is to find the index where 0 is stored in the array. Once the 0 is found, consider that index as a pivot. Move all the negative values to the left side of the pivot and thus the right side values will be positive automatically.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to rearrange the array, // such that all the negative appear // on the left side of 0 and all // positive appear on the right side of 0 void rearrangeArray( int arr[], int N) { int i, ind; // Find index of 0 for (i = 0; i < N; i++) { if (arr[i] == 0) { ind = i; break ; } } // Pivot the 0 element. int j = -1, k, temp; for (k = 0; k < N; k++) { if (arr[k] < 0) { j += 1; // Don't swap with pivot. if (arr[j] == 0) j += 1; swap(arr[j], arr[k]); } } // swap the pivot with last negative. swap(arr[ind], arr[j]); for ( int i = 0; i < N; i++) { cout << arr[i] << " " ; } } // Driver Code int main() { int arr[] = { 1, 0, -2, 3, 4, -5, -7, 9, -3 }; int N = sizeof (arr) / sizeof ( int ); rearrangeArray(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to rearrange the array, // such that all the negative appear // on the left side of 0 and all // positive appear on the right side of 0 static void rearrangeArray( int arr[], int N) { int i, ind = - 1 ; // Find index of 0 for (i = 0 ; i < N; i++) { if (arr[i] == 0 ) { ind = i; break ; } } // Pivot the 0 element. int j = - 1 , k, temp; for (k = 0 ; k < N; k++) { if (arr[k] < 0 ) { j += 1 ; // Don't swap with pivot. if (arr[j] == 0 ) j += 1 ; //swap temp = arr[j]; arr[j] = arr[k]; arr[k] = temp; } } // swap the pivot with last negative. int temp2 = arr[j]; arr[j] = arr[ind]; arr[ind] = temp2; for (j = 0 ; j < N; j++) { System.out.print(arr[j] + " " ); } } // Driver Code public static void main (String[] args) { int arr[] = { 1 , 0 , - 2 , 3 , 4 , - 5 , - 7 , 9 , - 3 }; int N = arr.length; rearrangeArray(arr, N); } } // This code is contributed by hrithikgarg03188 |
Python3
# Python code for the above approach # Function to rearrange the array, # such that all the negative appear # on the left side of 0 and all # positive appear on the right side of 0 def rearrangeArray(arr, N): ind = None # Find index of 0 for i in range (N): if (arr[i] = = 0 ): ind = i; break ; # Pivot the 0 element. j = - 1 temp = None for k in range (N): if (arr[k] < 0 ): j + = 1 ; # Don't swap with pivot. if (arr[j] = = 0 ): j + = 1 ; temp = arr[j]; arr[j] = arr[k]; arr[k] = temp; # swap the pivot with last negative. temp = arr[ind]; arr[ind] = arr[j]; arr[j] = temp; for i in range (N): print (arr[i], end = " " ); # Driver Code arr = [ 1 , 0 , - 2 , 3 , 4 , - 5 , - 7 , 9 , - 3 ]; N = len (arr) rearrangeArray(arr, N); # This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approach using System; class GFG { // Function to rearrange the array, // such that all the negative appear // on the left side of 0 and all // positive appear on the right side of 0 static void rearrangeArray( int [] arr, int N) { int i, ind = -1; // Find index of 0 for (i = 0; i < N; i++) { if (arr[i] == 0) { ind = i; break ; } } // Pivot the 0 element. int j = -1, k, temp; for (k = 0; k < N; k++) { if (arr[k] < 0) { j += 1; // Don't swap with pivot. if (arr[j] == 0) j += 1; //swap temp = arr[j]; arr[j] = arr[k]; arr[k] = temp; } } // swap the pivot with last negative. int temp2 = arr[j]; arr[j] = arr[ind]; arr[ind] = temp2; for (j = 0; j < N; j++) { Console.Write(arr[j] + " " ); } } // Driver Code public static void Main() { int [] arr = { 1, 0, -2, 3, 4, -5, -7, 9, -3 }; int N = arr.Length; rearrangeArray(arr, N); } } // This code is contributed by gfgking |
Javascript
<script> // JavaScript code for the above approach // Function to rearrange the array, // such that all the negative appear // on the left side of 0 and all // positive appear on the right side of 0 function rearrangeArray(arr, N) { let i, ind; // Find index of 0 for (i = 0; i < N; i++) { if (arr[i] == 0) { ind = i; break ; } } // Pivot the 0 element. let j = -1, k, temp; for (k = 0; k < N; k++) { if (arr[k] < 0) { j += 1; // Don't swap with pivot. if (arr[j] == 0) j += 1; let temp = arr[j]; arr[j] = arr[k]; arr[k] = temp; } } // swap the pivot with last negative. temp = arr[ind]; arr[ind] = arr[j]; arr[j] = temp; for (let i = 0; i < N; i++) { document.write(arr[i] + " " ); } } // Driver Code let arr = [1, 0, -2, 3, 4, -5, -7, 9, -3]; let N = arr.length; rearrangeArray(arr, N); // This code is contributed by Potta Lokesh </script> |
-2 -3 -5 -7 0 1 3 9 4
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us