Segregate positive and negative numbers in array
The problem at hand involves segregating positive and negative numbers in an array. The goal is to rearrange the elements in such a way that all negative numbers appear before the positive ones while maintaining their relative order within each group. This can be achieved without using any extra space, and the time complexity of the solution is a crucial factor to consider.
Problem Statement and Description
Given an array containing a mix of positive and negative integers, the task is to rearrange the array in such a way
that all negative numbers are placed before the positive numbers. However, the order of elements within each group
(negative or positive) should remain the same. For instance, consider the array:
[6, -3, 5, 2, 1, 8, -7, -2, -8, -6, 1, 3, -1]
. After rearranging, the array should look like this:
[-3, -7, -2, -8, -6, -1, 6, 5, 2, 1, 8, 1, 3]
.
Example
Let's understand the problem with a suitable example. Consider the array
[6, -3, 5, 2, 1, 8, -7, -2, -8, -6, 1, 3, -1]
. The initial arrangement is a mix of positive and
negative numbers:
6 -3 5 2 1 8 -7 -2 -8 -6 1 3 -1
The desired rearrangement involves segregating negative and positive numbers, while preserving their relative order within each group:
-3 -7 -2 -8 -6 -1 6 5 2 1 8 1 3
Idea to Solve
The problem can be solved using the Two-Pointer approach. The main idea is to maintain two pointers, one starting from the beginning of the array and the other starting from the end of the array. The pointers will move towards each other, swapping elements when necessary to ensure the negative numbers are on the left side and positive numbers are on the right side.
Pseudocode
arrange(arr[], size):
i = 0
j = size - 1
while i < j:
if arr[j] < 0:
if arr[i] >= 0:
swap(arr, i, j)
i++
j--
else:
i++
else:
j--
Algorithm Explanation
- Initialize two pointers
i
andj
to 0 andsize - 1
respectively, wheresize
is the number of elements in the array. - While
i
is less thanj
, perform the following steps:- If the element at index
j
is negative, check the element at indexi
.- If the element at index
i
is non-negative, swap the elements at indicesi
andj
, and incrementi
and decrementj
. - If the element at index
i
is negative, just incrementi
.
- If the element at index
- If the element at index
j
is positive, decrementj
.
- If the element at index
- Continue the process until
i
becomes greater than or equal toj
.
Code Solution
//C Program
//Segregate positive and negative numbers in array
#include <stdio.h>
//Swap the value of array elements
void swap(int arr[],int start,int end)
{
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
}
//Separating the negative and positive integer elements
void arrange(int arr[],int size)
{
if(size<=1)
{
return;
}
int i=0,j=size-1;
while(i<j)
{
if(arr[j]<0 )
{
if(arr[i]>=0)
{
//shift positive elements at the end
swap(arr,i,j);
i++;
j--;
}
else
{
i++;
}
}else
{
j--;
}
}
}
//Display array element
void display(int arr[],int size)
{
for(int i=0;i<size;i++)
{
printf(" %d",arr[i] );
}
printf("\n");
}
int main()
{
//Define array elements
int arr[]={6, -3, 5, 2, 1,8, -7,-2, -8, -6, 1, 3, -1};
//Get the size of array
int size=sizeof(arr)/sizeof(arr[0]);
printf(" Before Arrange : \n");
display(arr,size);
arrange(arr,size);
printf(" Before Arrange : \n");
display(arr,size);
return 0;
}
Output
Before Arrange :
6 -3 5 2 1 8 -7 -2 -8 -6 1 3 -1
Before Arrange :
-1 -3 -6 -8 -2 -7 8 1 2 5 1 3 6
/*
C++ Program
Segregate positive and negative numbers in array
*/
#include<iostream>
using namespace std;
class MyArray {
public:
//Swap the value of array elements
void swap(int arr[], int start, int end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
//Separating the negative and positive integer elements
void arrange(int arr[], int size) {
if (size <= 1) {
return;
}
int i = 0, j = size - 1;
while (i < j) {
if (arr[j] < 0) {
if (arr[i] >= 0) {
//shift positive elements at the end
this->swap(arr, i, j);
i++;
j--;
} else {
i++;
}
} else {
j--;
}
}
}
//Display array element values
void dispay(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << arr[i];
}
cout << "\n";
}
};
int main() {
MyArray obj = MyArray();
int arr[] = {
6,
-3,
5,
2,
1,
8,
-7,
-2,
-8,
-6,
1,
3,
-1
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
cout << " Before Arrange : \n";
obj.dispay(arr, size);
//here 2 indicate sorted element value
obj.arrange(arr, size);
cout << " After Arrange : \n";
obj.dispay(arr, size);
return 0;
}
Output
Before Arrange :
6 -3 5 2 1 8 -7 -2 -8 -6 1 3 -1
After Arrange :
-1 -3 -6 -8 -2 -7 8 1 2 5 1 3 6
/*
Java Program
Segregate positive and negative numbers in array
*/
public class MyArray
{
//Swap the value of array elements
public void swap(int []arr,int start,int end)
{
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
}
//Separating the negative and positive integer elements
public void arrange(int []arr,int size)
{
if(size<=1)
{
return;
}
int i=0,j=size-1;
while(i<j)
{
if(arr[j]<0 )
{
if(arr[i]>=0)
{
//shift positive elements at the end
swap(arr,i,j);
i++;
j--;
}
else
{
i++;
}
}else
{
j--;
}
}
}
//Display array element values
public void dispay(int []arr,int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" "+arr[i] );
}
System.out.print("\n");
}
public static void main(String[] args) {
MyArray obj = new MyArray();
//Define the value of array elements
int []arr = {6, -3, 5, 2, 1,8, -7,-2, -8, -6, 1, 3, -1};
//Get the size of array
int size = arr.length;
System.out.print(" Before Arrange : \n");
obj.dispay(arr,size);
//here 2 indicate sorted element value
obj.arrange(arr,size);
System.out.print(" After Arrange : \n");
obj.dispay(arr,size);
}
}
Output
Before Arrange :
6 -3 5 2 1 8 -7 -2 -8 -6 1 3 -1
After Arrange :
-1 -3 -6 -8 -2 -7 8 1 2 5 1 3 6
/*
C# Program
Segregate positive and negative numbers in array
*/
using System;
public class MyArray {
//Swap the value of array elements
public void swap(int[] arr, int start, int end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
//Separating the negative and positive integer elements
public void arrange(int[] arr, int size) {
if (size <= 1) {
return;
}
int i = 0, j = size - 1;
while (i < j) {
if (arr[j] < 0) {
if (arr[i] >= 0) {
swap(arr, i, j);
i++;
j--;
} else {
i++;
}
} else {
j--;
}
}
}
//Display array element values
public void dispay(int[] arr, int size) {
for (int i = 0; i < size; ++i) {
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
int[]
//Define the value of array elements
arr = {
6,
-3,
5,
2,
1,
8,
-7,
-2,
-8,
-6,
1,
3,
-1
};
//Get the size of array
int size = arr.Length;
Console.Write(" Before Arrange : \n");
obj.dispay(arr, size);
obj.arrange(arr, size);
Console.Write(" After Arrange : \n");
obj.dispay(arr, size);
}
}
Output
Before Arrange :
6 -3 5 2 1 8 -7 -2 -8 -6 1 3 -1
After Arrange :
-1 -3 -6 -8 -2 -7 8 1 2 5 1 3 6
<?php
/*
Php Program
Segregate positive and negative numbers in array
*/
class MyArray {
//Swap the value of array elements
public function swap(&$arr, $start, $end) {
$temp = $arr[$start];
$arr[$start] = $arr[$end];
$arr[$end] = $temp;
}
//Separating the negative and positive integer elements
public function arrange(&$arr, $size) {
if ($size <= 1) {
return;
}
$i = 0;
$j = $size - 1;
while ($i < $j) {
if ($arr[$j] < 0) {
if ($arr[$i] >= 0) {
//shift positive elements at the end
$this->swap($arr, $i, $j);
$i++;
$j--;
} else {
$i++;
}
} else {
$j--;
}
}
}
//Display array element values
public function dispay($arr, $size) {
for ($i = 0; $i < $size; ++$i) {
echo(" ". $arr[$i]);
}
echo("\n");
}
}
function main() {
$obj = new MyArray();
//Define the value of array elements
$arr = array(6, -3, 5, 2, 1, 8, -7, -2, -8, -6, 1, 3, -1);
//Get the size of array
$size = count($arr);
echo(" Before Arrange : \n");
$obj->dispay($arr, $size);
//here 2 indicate sorted element value
$obj->arrange($arr, $size);
echo(" After Arrange : \n");
$obj->dispay($arr, $size);
}
main();
Output
Before Arrange :
6 -3 5 2 1 8 -7 -2 -8 -6 1 3 -1
After Arrange :
-1 -3 -6 -8 -2 -7 8 1 2 5 1 3 6
/*
Node Js Program
Segregate positive and negative numbers in array
*/
class MyArray {
//Swap the value of array elements
swap(arr, start, end) {
var temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
//Separating the negative and positive integer elements
arrange(arr, size) {
if (size <= 1) {
return;
}
var i = 0;
var j = size - 1;
while (i < j) {
if (arr[j] < 0) {
if (arr[i] >= 0) {
//shift positive elements at the end
this.swap(arr, i, j);
i++;
j--;
} else {
i++;
}
} else {
j--;
}
}
}
//Display array element values
dispay(arr, size) {
for (var i = 0; i < size; ++i) {
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
}
function main(args) {
var obj = new MyArray();
//Define the value of array elements
var arr = [6, -3, 5, 2, 1, 8, -7, -2, -8, -6, 1, 3, -1];
//Get the size of array
var size = arr.length;
process.stdout.write(" Before Arrange : \n");
obj.dispay(arr, size);
//here 2 indicate sorted element value
obj.arrange(arr, size);
process.stdout.write(" After Arrange : \n");
obj.dispay(arr, size);
}
main();
Output
Before Arrange :
6 -3 5 2 1 8 -7 -2 -8 -6 1 3 -1
After Arrange :
-1 -3 -6 -8 -2 -7 8 1 2 5 1 3 6
# Python 3 Program
# Segregate positive and negative numbers in array
class MyArray :
# Swap the value of array elements
def swap(self, arr, start, end) :
temp = arr[start]
arr[start] = arr[end]
arr[end] = temp
# Separating the negative and positive integer elements
def arrange(self, arr, size) :
if (size <= 1) :
return
i = 0
j = size - 1
while (i < j) :
if (arr[j] < 0) :
if (arr[i] >= 0) :
self.swap(arr, i, j)
i += 1
j -= 1
else :
i += 1
else :
j -= 1
# Display array element values
def dispay(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print("\n", end = "")
def main() :
obj = MyArray()
arr = [6, -3, 5, 2, 1, 8, -7, -2, -8, -6, 1, 3, -1]
size = len(arr)
print(" Before Arrange : \n", end = "")
obj.dispay(arr, size)
obj.arrange(arr, size)
print(" After Arrange : \n", end = "")
obj.dispay(arr, size)
if __name__ == "__main__":
main()
Output
Before Arrange :
6 -3 5 2 1 8 -7 -2 -8 -6 1 3 -1
After Arrange :
-1 -3 -6 -8 -2 -7 8 1 2 5 1 3 6
# Ruby Program
# Segregate positive and negative numbers in array
class MyArray
# Swap the value of array elements
def swap(arr, start, last)
temp = arr[start]
arr[start] = arr[last]
arr[last] = temp
end
# Separating the negative and positive integer elements
def arrange(arr, size)
if (size <= 1)
return
end
i = 0
j = size - 1
while (i < j)
if (arr[j] < 0)
if (arr[i] >= 0)
self.swap(arr, i, j)
i += 1
j -= 1
else
i += 1
end
else
j -= 1
end
end
end
# Display array element values
def dispay(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
end
def main()
obj = MyArray.new()
arr = [6, -3, 5, 2, 1, 8, -7, -2, -8, -6, 1, 3, -1]
size = arr.length
print(" Before Arrange :\n")
obj.dispay(arr, size)
obj.arrange(arr, size)
print(" After Arrange :\n")
obj.dispay(arr, size)
end
main()
Output
Before Arrange :
6 -3 5 2 1 8 -7 -2 -8 -6 1 3 -1
After Arrange :
-1 -3 -6 -8 -2 -7 8 1 2 5 1 3 6
/*
Scala Program
Segregate positive and negative numbers in array
*/
class MyArray {
//Swap the value of array elements
def swap(arr: Array[Int], start: Int, end: Int): Unit = {
val temp: Int = arr(start);
arr(start) = arr(end);
arr(end) = temp;
}
//Separating the negative and positive integer elements
def arrange(arr: Array[Int], size: Int): Unit = {
if (size <= 1) {
return;
}
var i: Int = 0;
var j: Int = size - 1;
while (i < j) {
if (arr(j) < 0) {
if (arr(i) >= 0) {
this.swap(arr, i, j);
i += 1;
j -= 1;
} else {
i += 1;
}
} else {
j -= 1;
}
}
}
//Display array element values
def dispay(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
print("\n");
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
val arr: Array[Int] = Array(6, -3, 5, 2, 1, 8, -7, -2, -8, -6, 1, 3, -1);
val size: Int = arr.length;
print(" Before Arrange : \n");
obj.dispay(arr, size);
obj.arrange(arr, size);
print(" After Arrange : \n");
obj.dispay(arr, size);
}
}
Output
Before Arrange :
6 -3 5 2 1 8 -7 -2 -8 -6 1 3 -1
After Arrange :
-1 -3 -6 -8 -2 -7 8 1 2 5 1 3 6
/*
Swift Program
Segregate positive and negative numbers in array
*/
class MyArray {
//Swap the value of array elements
func swap(_ arr: inout [Int], _ start: Int, _ end: Int) {
let temp: Int = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
//Separating the negative and positive integer elements
func arrange(_ arr: inout [Int], _ size: Int) {
if (size <= 1) {
return;
}
var i: Int = 0;
var j: Int = size - 1;
while (i < j) {
if (arr[j] < 0) {
if (arr[i] >= 0) {
self.swap(&arr, i, j);
i += 1;
j -= 1;
} else {
i += 1;
}
} else {
j -= 1;
}
}
}
//Display array element values
func dispay(_ arr: [Int], _ size: Int) {
var i: Int = 0;
while (i < size) {
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
func main() {
let obj: MyArray = MyArray();
var arr: [Int] = [6, -3, 5, 2, 1, 8, -7, -2, -8, -6, 1, 3, -1];
let size: Int = arr.count;
print(" Before Arrange : \n", terminator: "");
obj.dispay(arr, size);
obj.arrange(&arr, size);
print(" After Arrange : \n", terminator: "");
obj.dispay(arr, size);
}
main();
Output
Before Arrange :
6 -3 5 2 1 8 -7 -2 -8 -6 1 3 -1
After Arrange :
-1 -3 -6 -8 -2 -7 8 1 2 5 1 3 6
Time Complexity
The time complexity of this algorithm is linear, O(n), where n is the number of elements in the array. The algorithm iterates through the array once, and each iteration involves constant time operations (swapping, comparisons, and increments/decrements). As a result, the algorithm is efficient even for large arrays.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment