Move all negative numbers to beginning and positive to end with constant extra space

Last Updated : 19 Sep, 2023

An array contains both positive and negative numbers in random order. Rearrange the array elements so that all negative numbers appear before all positive numbers.

Examples :

Input: -12, 11, -13, -5, 6, -7, 5, -3, -6
Output: -12 -13 -5 -7 -3 -6 11 6 5

Note: Order of elements is not important here.

Naive approach: The idea is to sort the array of elements, this will make sure that all the negative elements will come before all the positive elements.
Below is the implementation of the above approach:

C++

#include <iostream> 
#include<vector> 
#include<algorithm> 
using namespace std; 
void move(vector<int>& arr){ 
  sort(arr.begin(),arr.end()); 
} 
int main() { 
  
    vector<int> arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 }; 
      move(arr); 
    for (int e : arr) 
       cout<<e << " "; 
    return 0; 
} 
  
// This code is contributed by repakaeshwaripriya

Java

// Java program to move all negative numbers to the 
// beginning and all positive numbers to the end with 
// constant extra space 
import java.util.*; 
public class Gfg { 
     
    public static void move(int[] arr) 
    { 
        Arrays.sort(arr); 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        int[] arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 }; 
        move(arr); 
        for (int e : arr) 
            System.out.print(e + " "); 
    } 
} 
// This article is contributed by aadityapburujwale

Python3

# Python code for the same approach 
def move(arr): 
  arr.sort() 
  
# driver code 
arr = [ -1, 2, -3, 4, 5, 6, -7, 8, 9 ] 
move(arr) 
for e in arr: 
    print(e , end = " ") 
  
# This code is contributed by shinjanpatra

C#

// C# program to move all negative numbers to the 
// beginning and all positive numbers to the end with 
// constant extra space 
using System; 
using System.Collections; 
public class Gfg { 
     
    public static void move(int[] arr) 
    { 
        Array.Sort(arr); 
    } 
  
    // Driver code 
    public static void Main() 
    { 
        int[] arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 }; 
        move(arr); 
        foreach (int e in arr) 
            Console.Write(e + " "); 
    } 
} 
// This code is contributed by Saurabh Jaiswal

Javascript

<script> 
  
// JavaScript Code for the same approach 
  
function move(arr){ 
    arr.sort(); 
} 
  
// driver code 
    
let arr = [ -1, 2, -3, 4, 5, 6, -7, 8, 9 ]; 
move(arr); 
for (let e of arr) 
    document.write(e , " "); 
    
// This code is contributed by shinjanpatra 
  
</script>

Output

-7 -3 -1 2 4 5 6 8 9

Time Complexity: O(n*log(n)), Where n is the length of the given array.
Auxiliary Space: O(1)

Efficient Approach 1:
The idea is to simply apply the partition process of quicksort.

C++

// A C++ program to put all negative 
// numbers before positive numbers 
#include <bits/stdc++.h> 
using namespace std; 
  
void rearrange(int arr[], int n) 
{ 
    int j = 0; 
    for (int i = 0; i < n; i++) { 
        if (arr[i] < 0) { 
            if (i != j) 
                swap(arr[i], arr[j]); 
            j++; 
        } 
    } 
} 
  
// A utility function to print an array 
void printArray(int arr[], int n) 
{ 
    for (int i = 0; i < n; i++) 
        printf("%d ", arr[i]); 
} 
  
// Driver code 
int main() 
{ 
    int arr[] = { -1, 2, -3, 4, 5, 6, -7, 8, 9 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    rearrange(arr, n); 
    printArray(arr, n); 
    return 0; 
} 

Java

// Java program to put all negative 
// numbers before positive numbers 
import java.io.*; 
  
class GFG { 
  
    static void rearrange(int arr[], int n) 
    { 
        int j = 0, temp; 
        for (int i = 0; i < n; i++) { 
            if (arr[i] < 0) { 
                if (i != j) { 
                    temp = arr[i]; 
                    arr[i] = arr[j]; 
                    arr[j] = temp; 
                } 
                j++; 
            } 
        } 
    } 
  
    // A utility function to print an array 
    static void printArray(int arr[], int n) 
    { 
        for (int i = 0; i < n; i++) 
            System.out.print(arr[i] + " "); 
    } 
  
    // Driver code 
    public static void main(String args[]) 
    { 
        int arr[] = { -1, 2, -3, 4, 5, 6, -7, 8, 9 }; 
        int n = arr.length; 
  
        rearrange(arr, n); 
        printArray(arr, n); 
    } 
} 
  
// This code is contributed by Nikita Tiwari. 

Python3

# A Python 3 program to put 
# all negative numbers before 
# positive numbers 
  
def rearrange(arr, n ) : 
  
    # Please refer partition() in  
    # below post 
    # https://www.geeksforgeeks.org / quick-sort / j = 0 
    j = 0 
    for i in range(0, n) : 
        if (arr[i] < 0) : 
            temp = arr[i] 
            arr[i] = arr[j] 
            arr[j]= temp 
            j = j + 1
    print(arr) 
  
# Driver code 
arr = [-1, 2, -3, 4, 5, 6, -7, 8, 9] 
n = len(arr) 
rearrange(arr, n) 
  
  
# This code is contributed by Nikita Tiwari. 

C#

// C# program to put all negative 
// numbers before positive numbers 
using System; 
  
class GFG { 
    static void rearrange(int[] arr, int n) 
    { 
  
        int j = 0, temp; 
        for (int i = 0; i < n; i++) { 
            if (arr[i] < 0) { 
                temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
                j++; 
            } 
        } 
    } 
  
    // A utility function to print an array 
    static void printArray(int[] arr, int n) 
    { 
        for (int i = 0; i < n; i++) 
            Console.Write(arr[i] + " "); 
    } 
  
    // Driver code 
    public static void Main() 
    { 
        int[] arr = { -1, 2, -3, 4, 5, 6, -7, 8, 9 }; 
        int n = arr.Length; 
  
        rearrange(arr, n); 
        printArray(arr, n); 
    } 
} 
  
// This code is contributed by nitin mittal. 

Javascript

<script> 
// A JavaScript program to put all negative 
// numbers before positive numbers 
  
function rearrange(arr, n) 
{ 
    let j = 0; 
    for (let i = 0; i < n; i++) { 
        if (arr[i] < 0) { 
            if (i != j){ 
                let temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
            j++; 
        } 
    } 
} 
  
// A utility function to print an array 
function printArray(arr, n) 
{ 
    for (let i = 0; i < n; i++) 
        document.write(arr[i] + " "); 
} 
  
// Driver code 
    let arr = [ -1, 2, -3, 4, 5, 6, -7, 8, 9 ]; 
    let n = arr.length; 
    rearrange(arr, n); 
    printArray(arr, n); 
  
  
  
  
// This code is contributed by Surbhi Tyagi. 
</script>

PHP

<?php  
// A PHP program to put all negative 
// numbers before positive numbers 
  
function rearrange(&$arr, $n) 
{ 
    $j = 0; 
    for ($i = 0; $i < $n; $i++) 
    { 
        if ($arr[$i] < 0)  
        { 
            if ($i != $j) 
            { 
                $temp = $arr[$i]; 
                $arr[$i] = $arr[$j]; 
                $arr[$j] = $temp; 
            } 
            $j++; 
        } 
    } 
} 
  
// A utility function to print an array 
function printArray(&$arr, $n) 
{ 
    for ($i = 0; $i < $n; $i++) 
        echo $arr[$i]." "; 
} 
  
// Driver code 
$arr = array(-1, 2, -3, 4, 5, 6, -7, 8, 9 ); 
$n = sizeof($arr); 
rearrange($arr, $n); 
printArray($arr, $n); 
  
// This code is contributed by ChitraNayal 
?> 

Output

-1 -3 -7 4 5 6 2 8 9

Time complexity: O(N)
Auxiliary Space: O(1)

Two Pointer Approach: The idea is to solve this problem with constant space and linear time is by using a two-pointer or two-variable approach where we simply take two variables like left and right which hold the 0 and N-1 indexes. Just need to check that :

Check If the left and right pointer elements are negative then simply increment the left pointer.
Otherwise, if the left element is positive and the right element is negative then simply swap the elements, and simultaneously increment and decrement the left and right pointers.
Else if the left element is positive and the right element is also positive then simply decrement the right pointer.
Repeat the above 3 steps until the left pointer ? right pointer.

Below is the implementation of the above approach:

C++

// C++ program of the above  
// approach 
  
#include <iostream> 
using namespace std; 
  
// Function to shift all the 
// negative elements on left side 
void shiftall(int arr[], int left,  
              int right) 
{ 
    
  // Loop to iterate over the  
  // array from left to the right 
  while (left<=right) 
  { 
    // Condition to check if the left 
    // and the right elements are  
    // negative 
    if (arr[left] < 0 && arr[right] < 0) 
      left+=1; 
      
    // Condition to check if the left  
    // pointer element is positive and  
    // the right pointer element is negative 
    else if (arr[left]>0 && arr[right]<0) 
    { 
      int temp=arr[left]; 
      arr[left]=arr[right]; 
      arr[right]=temp; 
      left+=1; 
      right-=1; 
    } 
      
    // Condition to check if both the  
    // elements are positive 
    else if (arr[left]>0 && arr[right] >0) 
      right-=1; 
    else{ 
      left += 1; 
      right -= 1; 
    } 
  } 
} 
  
// Function to print the array 
void display(int arr[], int right){ 
    
  // Loop to iterate over the element 
  // of the given array 
  for (int i=0;i<=right;++i){ 
    cout<<arr[i]<<" "; 
  } 
  cout<<endl; 
} 
  
// Driver Code 
int main()  
{ 
  int arr[] = {-12, 11, -13, -5,  
               6, -7, 5, -3, 11}; 
  int arr_size = sizeof(arr) /  
                sizeof(arr[0]); 
    
  // Function Call 
  shiftall(arr,0,arr_size-1); 
  display(arr,arr_size-1); 
  return 0; 
} 
  
//added by Dhruv Goyal

Java

// Java program of the above 
// approach 
import java.io.*; 
  
class GFG{ 
  
// Function to shift all the 
// negative elements on left side 
static void shiftall(int[] arr, int left, 
                     int right) 
{ 
      
    // Loop to iterate over the 
    // array from left to the right 
    while (left <= right)  
    { 
          
        // Condition to check if the left 
        // and the right elements are 
        // negative 
        if (arr[left] < 0 && arr[right] < 0) 
            left++; 
  
        // Condition to check if the left 
        // pointer element is positive and 
        // the right pointer element is negative 
        else if (arr[left] > 0 && arr[right] < 0) 
        { 
            int temp = arr[left]; 
            arr[left] = arr[right]; 
            arr[right] = temp; 
            left++; 
            right--; 
        } 
  
        // Condition to check if both the 
        // elements are positive 
        else if (arr[left] > 0 && arr[right] > 0) 
            right--; 
        else
        { 
            left++; 
            right--; 
        } 
    } 
} 
  
// Function to print the array 
static void display(int[] arr, int right) 
{ 
      
    // Loop to iterate over the element 
    // of the given array 
    for(int i = 0; i <= right; ++i) 
        System.out.print(arr[i] + " "); 
          
    System.out.println(); 
} 
  
// Drive code 
public static void main(String[] args) 
{ 
    int[] arr = { -12, 11, -13, -5,  
                   6, -7, 5, -3, 11 }; 
                     
    int arr_size = arr.length; 
  
    // Function Call 
    shiftall(arr, 0, arr_size - 1); 
    display(arr, arr_size - 1); 
} 
} 
  
// This code is contributed by dhruvgoyal267

Python3

# Python3 program of the  
# above approach 
  
# Function to shift all the  
# the negative elements to 
# the left of the array 
def shiftall(arr,left,right): 
    
  # Loop to iterate while the  
  # left pointer is less than 
  # the right pointer 
  while left<=right: 
      
    # Condition to check if the left 
    # and right pointer negative 
    if arr[left] < 0 and arr[right] < 0: 
      left+=1
        
    # Condition to check if the left  
    # pointer element is positive and  
    # the right pointer element is 
    # negative 
    else if arr[left]>0 and arr[right]<0: 
      arr[left], arr[right] = \ 
              arr[right],arr[left] 
      left+=1
      right-=1
        
    # Condition to check if the left 
    # pointer is positive and right  
    # pointer as well 
    else if arr[left]>0 and arr[right]>0: 
      right-=1
    else: 
      left+=1
      right-=1
        
# Function to print the array 
def display(arr): 
  for i in range(len(arr)): 
    print(arr[i], end=" ") 
  print() 
  
# Driver Code 
if __name__ == "__main__": 
  arr=[-12, 11, -13, -5, \ 
       6, -7, 5, -3, 11] 
  n=len(arr) 
  shiftall(arr,0,n-1) 
  display(arr) 
  
# Sumit Singh

C#

// C# program of the above 
// approach 
using System.IO; 
using System; 
class GFG 
{ 
    // Function to shift all the 
    // negative elements on left side 
    static void shiftall(int[] arr, int left,int right) 
    { 
        
        // Loop to iterate over the 
        // array from left to the right 
        while (left <= right)  
        { 
           
            // Condition to check if the left 
            // and the right elements are 
            // negative 
            if (arr[left] < 0 && arr[right] < 0) 
                left++; 
   
            // Condition to check if the left 
            // pointer element is positive and 
            // the right pointer element is negative 
            else if (arr[left] > 0 && arr[right] < 0) 
            { 
                int temp = arr[left]; 
                arr[left] = arr[right]; 
                arr[right] = temp; 
                left++; 
                right--; 
            } 
   
            // Condition to check if both the 
            // elements are positive 
            else if (arr[left] > 0 && arr[right] > 0) 
                right--; 
            else
            { 
                left++; 
                right--; 
            } 
        } 
    } 
    
    // Function to print the array 
    static void display(int[] arr, int right) 
    { 
        
        // Loop to iterate over the element 
        // of the given array 
        for(int i = 0; i <= right; ++i) 
        { 
            Console.Write(arr[i] + " "); 
              
        } 
        Console.WriteLine(); 
    } 
      
    // Drive code                    
    static void Main() 
    { 
        int[] arr = {-12, 11, -13, -5, 6, -7, 5, -3, 11}; 
        int arr_size = arr.Length; 
        shiftall(arr, 0, arr_size - 1); 
        display(arr, arr_size - 1); 
    } 
} 
  
// This code is contributed by avanitrachhadiya2155 

Javascript

<script> 
  
// Javascript program of the above  
// approach 
  
// Function to shift all the 
// negative elements on left side 
function shiftall(arr, left, right) 
{ 
      
    // Loop to iterate over the  
    // array from left to the right 
    while (left <= right) 
    { 
          
        // Condition to check if the left 
        // and the right elements are  
        // negative 
        if (arr[left] < 0 && arr[right] < 0) 
            left += 1; 
          
        // Condition to check if the left  
        // pointer element is positive and  
        // the right pointer element is negative 
        else if(arr[left] > 0 && arr[right] < 0) 
        { 
            let temp = arr[left]; 
            arr[left] = arr[right]; 
            arr[right] = temp; 
            left += 1; 
            right -= 1; 
        } 
          
        // Condition to check if both the  
        // elements are positive 
        else if (arr[left] > 0 && arr[right] > 0) 
            right -= 1; 
        else
        { 
            left += 1; 
            right -= 1; 
        } 
    } 
} 
  
// Function to print the array 
function display(arr, right) 
{ 
      
    // Loop to iterate over the element 
    // of the given array 
    for(let i = 0; i < right; i++) 
        document.write(arr[i] + " "); 
} 
  
// Driver Code 
let arr = [ -12, 11, -13, -5,  
             6, -7, 5, -3, 11 ]; 
let arr_size = arr.length; 
  
// Function Call 
shiftall(arr, 0, arr_size - 1); 
display(arr, arr_size); 
   
// This code is contributed by annianni 
  
</script>

Output

-12 -3 -13 -5 -7 6 5 11 11

This is an in-place rearranging algorithm for arranging the positive and negative numbers where the order of elements is not maintained.
Time Complexity: O(N)
Auxiliary Space: O(1)

The problem becomes difficult if we need to maintain the order of elements. Please refer to Rearrange positive and negative numbers with constant extra space for details.

If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeek’s main page and help other Geeks.

Approach 3:
Here, we will use the famous Dutch National Flag Algorithm for two “colors”. The first color will be for all negative integers and the second color will be for all positive integers. We will divide the array into three partitions with the help of two pointers, low and high.

ar[1…low-1] negative integers
ar[low…high] unknown
ar[high+1…N] positive integers

Now, we explore the array with the help of low pointer, shrinking the unknown partition, and moving elements to their correct partition in the process. We do this until we have explored all the elements, and size of the unknown partition shrinks to zero.

Below is the implementation of the above approach:

C++

#include <iostream> 
using namespace std; 
  
// Swap Function. 
void swap(int &a,int &b){ 
  int temp =a; 
  a=b; 
  b=temp; 
} 
    
// Using Dutch National Flag Algorithm. 
void reArrange(int arr[],int n){ 
      int low =0,high = n-1; 
      while(low<high){ 
      if(arr[low]<0){ 
          low++; 
      }else if(arr[high]>0){ 
          high--; 
      }else{ 
        swap(arr[low],arr[high]); 
      } 
    } 
} 
void displayArray(int arr[],int n){ 
  for(int i=0;i<n;i++){ 
    cout<<arr[i]<<" "; 
  } 
  cout<<endl; 
} 
int main() { 
    // Data 
    int arr[] = {1, 2,  -4, -5, 2, -7, 3, 2, -6, -8, -9, 3, 2,  1}; 
      int n = sizeof(arr)/sizeof(arr[0]); 
      reArrange(arr,n); 
    displayArray(arr,n); 
    return 0; 
} 

Java

// Java program to move all negative numbers to the 
// beginning and all positive numbers to the end with 
// constant extra space 
  
public class Gfg { 
  
    // a utility function to swap two elements of an array 
    public static void swap(int[] ar, int i, int j) 
    { 
        int t = ar[i]; 
        ar[i] = ar[j]; 
        ar[j] = t; 
    } 
  
    // function to shilf all negative integers to the left 
    // and all positive integers to the right 
    // using Dutch National Flag Algorithm 
    public static void move(int[] ar) 
    { 
        int low = 0; 
        int high = ar.length - 1; 
        while (low <= high) { 
            if (ar[low] <= 0) 
                low++; 
            else
                swap(ar, low, high--); 
        } 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        int[] ar = { 1, 2,  -4, -5, 2, -7, 3, 
                     2, -6, -8, -9, 3, 2,  1 }; 
        move(ar); 
        for (int e : ar) 
            System.out.print(e + " "); 
    } 
} 
  
// This code is contributed by Vedant Harshit

Python3

# Python code for the approach 
  
# Using Dutch National Flag Algorithm. 
def reArrange(arr, n): 
    low,high = 0, n - 1
    while(low<high): 
        if(arr[low] < 0): 
            low += 1
        elif(arr[high] > 0): 
            high -= 1
        else: 
            arr[low],arr[high] = arr[high],arr[low] 
  
def displayArray(arr, n): 
  
    for i in range(n): 
        print(arr[i],end = " ") 
    
    print('') 
  
# driver code 
# Data 
arr = [1, 2,  -4, -5, 2, -7, 3, 2, -6, -8, -9, 3, 2,  1] 
n = len(arr) 
reArrange(arr,n) 
displayArray(arr,n) 
  
# This code is contributed by shinjanpatra

C#

// Include namespace system 
using System; 
  
// C# program to move all negative numbers to the 
// beginning and all positive numbers to the end with 
// constant extra space 
public class Gfg 
{ 
  // a utility function to swap two elements of an array 
  public static void swap(int[] ar, int i, int j) 
  { 
    var t = ar[i]; 
    ar[i] = ar[j]; 
    ar[j] = t; 
  } 
  // function to shilf all negative integers to the left 
  // and all positive integers to the right 
  // using Dutch National Flag Algorithm 
  public static void move(int[] ar) 
  { 
    var low = 0; 
    var high = ar.Length - 1; 
    while (low <= high) 
    { 
      if (ar[low] <= 0) 
      { 
        low++; 
      } 
      else 
      { 
        Gfg.swap(ar, low, high--); 
      } 
    } 
  } 
  
  // Driver code 
  public static void Main(String[] args) 
  { 
    int[] ar = {1, 2, -4, -5, 2, -7, 3, 2, -6, -8, -9, 3, 2, 1}; 
    Gfg.move(ar); 
    foreach (int e in ar) 
    {            Console.Write(e.ToString() + " "); 
    } 
  } 
} 
  
// This code is contributed by mukulsomukesh

Javascript

<script> 
  
// JavaScript code for the approach 
  
// Using Dutch National Flag Algorithm. 
function reArrange(arr, n){ 
    let low = 0,high = n - 1 
    while(low<high){ 
        if(arr[low] < 0) 
            low += 1 
        else if(arr[high] > 0) 
            high -= 1 
        else{ 
            let temp = arr[low] 
            arr[low] = arr[high] 
            arr[high] = temp 
        } 
    } 
} 
  
function displayArray(arr, n){ 
  
    for(let i = 0; i < n; i++){ 
        document.write(arr[i]," ") 
    } 
    document.write('</br>') 
} 
  
// driver code 
// Data 
let arr = [1, 2,  -4, -5, 2, -7, 3, 2, -6, -8, -9, 3, 2,  1] 
let n = arr.length 
reArrange(arr,n) 
displayArray(arr,n) 
  
// This code is contributed by shinjanpatra 
  
</script>

Output

-9 -8 -4 -5 -6 -7 3 2 2 2 1 3 2 1

Time complexity: O(N)
Auxiliary Space: O(1)

The order of elements does not matter here. Explanation and code contributed by Vedant Harshit

Suggest improvement

Count of equal value pairs from given two Arrays such that a[i] equals b[j]

Share your thoughts in the comments

Two Pointers Technique in Different languages

Problems based on Two-Pointer Technique

Two Pointers Technique in Different languages

Problems based on Two-Pointer Technique

Move all negative numbers to beginning and positive to end with constant extra space

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

PHP

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?