Segregating negative and positive maintaining order and O(1) space

0 0 5 minutes read

Segregation of negative and positive numbers in an array without using extra space, and maintaining insertion order and in O(n^2) time complexity.

Examples:

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

Input :5
       11 -13 6 -7 5
Output :-13 -7 11 6 5

We have discussed this problem below posts.

ers-beginning-positive-end-constant-extra-space/”>Rearrange positive and negative numbers without maintaining order.
Rearrange positive and negative numbers with constant extra space

This post discusses a new approach that takes O(1) extra space. We first count total negative numbers, then move negative numbers one by one to the correct position.

Implementation:

C++

// C++ program to move all negative numbers
// to beginning and positive numbers to end
// keeping order.
#include <iostream>
using namespace std;
 
void segregate(int arr[], int n)
{
    // Count negative numbers
    int count_negative = 0;
    for (int i = 0; i < n; i++) 
        if (arr[i] < 0)
            count_negative++;    
 
    // Run a loop until all negative
    // numbers are moved to the beginning
    int i = 0, j = i + 1;
    while (i != count_negative) {
 
        // If number is negative, update
        // position of next positive number.
        if (arr[i] < 0) {
            i++;
            j = i + 1;
        }
 
        // If number is positive, move it to
        // index j and increment j.
        else if (arr[i] > 0 && j < n) {
            swap(arr[i], arr[j]);
            j++;
        }
    }
}
 
int main()
{
    int count_negative = 0;
    int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    segregate(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " "; 
}

Java

// Java program to move all 
// negative numbers to beginning 
// and positive numbers to end
// keeping order.
class GFG
{
static void segregate(int arr[], 
                      int n)
{
     
// Count negative numbers
int count_negative = 0;
for (int i = 0; i < n; i++) 
    if (arr[i] < 0)
        count_negative++; 
 
// Run a loop until all 
// negative numbers are 
// moved to the beginning
int i = 0, j = i + 1;
while (i != count_negative)
{
 
    // If number is negative, 
    // update position of next
    // positive number.
    if (arr[i] < 0) 
    {
        i++;
        j = i + 1;
    }
 
    // If number is positive, move 
    // it to index j and increment j.
    else if (arr[i] > 0 && j < n) 
    {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
        j++;
    }
}
}
 
// Driver code
public static void main(String[] args) 
{
    int count_negative = 0;
    int arr[] = { -12, 11, -13, -5,
                   6, -7, 5, -3, -6 };
    int n = arr.length;
    segregate(arr, n);
    for (int i = 0; i < n; i++)
        System.out.print(arr[i] + " "); 
}
} 
 
// This code is contributed 
// by ChitraNayal

C#

// C# program to move all 
// negative numbers to beginning
// and positive numbers to end
// keeping order.
using System;
 
class GFG
{
static void segregate(int[] arr, 
                      int n)
{
     
// Count negative numbers
int count_negative = 0,i;
for (i = 0; i < n; i++) 
    if (arr[i] < 0)
        count_negative++; 
 
// Run a loop until all 
// negative numbers are
// moved to the beginning
i = 0;
int j = i + 1;
while (i != count_negative) 
{
 
    // If number is negative, 
    // update position of next 
    // positive number.
    if (arr[i] < 0) 
    {
        i++;
        j = i + 1;
    }
 
    // If number is positive, move 
    // it to index j and increment j.
    else if (arr[i] > 0 && j < n)
    {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
        j++;
    }
}
}
 
// Driver code
public static void Main() 
{
    int[] arr = { -12, 11, -13, -5, 
                    6, -7, 5, -3, -6 };
    int n = arr.Length;
    segregate(arr, n);
    for (int i = 0; i < n; i++)
        Console.Write(arr[i] + " "); 
}
} 
 
// This code is contributed 
// by ChitraNayal

Python 3

# Python 3 program to move all 
# negative numbers to beginning
# and positive numbers to end
# keeping order.
 
def segregate(arr, n):
     
    # Count negative numbers
    count_negative = 0
    for i in range(n): 
        if (arr[i] < 0):
            count_negative += 1
 
    # Run a loop until all 
    # negative numbers are 
    # moved to the beginning
    i = 0
    j = i + 1
    while (i != count_negative):
 
        # If number is negative, 
        # update position of next 
        # positive number.
        if (arr[i] < 0) :
            i += 1
            j = i + 1
 
        # If number is positive, move 
        # it to index j and increment j.
        elif (arr[i] > 0 and j < n):
            t = arr[i]
            arr[i] = arr[j]
            arr[j] = t
            j += 1
         
# Driver Code
count_negative = 0
arr = [-12, 11, -13, -5, 
        6, -7, 5, -3, -6 ]
segregate(arr, 9)
for i in range(9):
    print(arr[i] , end =" ")
 
# This code is contributed
# by ChitraNayal

PHP

<?php 
// PHP program to move all 
// negative numbers to 
// beginning and positive 
// numbers to end keeping order.
 
function segregate(&$arr, $n)
{
    // Count negative numbers
    $count_negative = 0;
    for ($i = 0; $i < $n; $i++) 
        if ($arr[$i] < 0)
            $count_negative++; 
 
    // Run a loop until all 
    // negative numbers are
    // moved to the beginning
    $i = 0;
    $j = $i + 1;
    while ($i != $count_negative)
    {
 
        // If number is negative, 
        // update position of next
        // positive number.
        if ($arr[$i] < 0) 
        {
            $i++;
            $j = $i + 1;
        }
 
        // If number is positive, move 
        // it to index j and increment j.
        else if ($arr[$i] > 0 && $j < $n)
        {
            $t = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $t;
            $j++;
        }
    }
}
 
// Driver Code
$count_negative = 0;
$arr = array(-12, 11, -13, -5, 
              6, -7, 5, -3, -6);
$n = sizeof($arr);
segregate($arr, $n);
for ($i = 0; $i < $n; $i++)
    echo $arr[$i] ." "; 
     
// This code is contributed
// by ChitraNayal
?>

Javascript

<script>
// JavaScript program to move all negative numbers
// to beginning and positive numbers to end
// keeping order.
function segregate(arr, n)
{
 
    // Count negative numbers
    let count_negative = 0;
    for (let i = 0; i < n; i++)
        if (arr[i] < 0)
            count_negative++;    
 
    // Run a loop until all negative
    // numbers are moved to the beginning
    let i = 0, j = i + 1;
    while (i != count_negative) {
 
        // If number is negative, update
        // position of next positive number.
        if (arr[i] < 0) {
            i++;
            j = i + 1;
        }
 
        // If number is positive, move it to
        // index j and increment j.
        else if (arr[i] > 0 && j < n) {
            let t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            j++;
        }
    }
}
 
    let count_negative = 0;
    let arr = [ -12, 11, -13, -5, 6, -7, 5, -3, -6 ];
    let n = arr.length;
    segregate(arr, n);
    for (let i = 0; i < n; i++)
        document.write(arr[i] + " ");
 
// This code is contributed by Surbhi Tyagi.
</script>

Output

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

Complexity Analysis:

Time Complexity: O(n²)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!