Skip to main content

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

  1. Initialize two pointers i and j to 0 and size - 1 respectively, where size is the number of elements in the array.
  2. While i is less than j, perform the following steps:
    • If the element at index j is negative, check the element at index i.
      • If the element at index i is non-negative, swap the elements at indices i and j, and increment i and decrement j.
      • If the element at index i is negative, just increment i.
    • If the element at index j is positive, decrement j.
  3. Continue the process until i becomes greater than or equal to j.

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.

Last updated on by Kalkicode




Comment

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