Move all negative elements at the beginning of array

Moving all negative elements to the beginning of an array is a common problem in programming. The task involves rearranging the elements in a way that all the negative numbers appear before the non-negative (positive and zero) numbers, while maintaining their original relative order within the negative and non-negative subarrays.

Problem Statement

Given an array of integers, rearrange the elements so that all the negative elements appear at the beginning of the array, followed by the non-negative elements, while preserving their original order within each subarray.

Example

Consider the following array:

arr = [2, -1, 0, -2, 1, 8, -7, 3, 5, 9, 4, 2, -5, 10, -9]

After moving the negative elements to the beginning:

arr = [-1, -2, -7, -5, -9, 2, 0, 1, 8, 3, 5, 9, 4, 2, 10]

Idea to Solve

The general idea to solve this problem is to use two pointers: one starting from the left side of the array (for negative elements) and the other starting from the right side (for non-negative elements). The pointers gradually move towards each other, swapping elements as needed to separate the negative and non-negative elements.

Pseudocode

function swap_element(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

function separate_elements(arr, size):
    j = 0
    i = size - 1
    while i > j:
        if arr[i] < 0 and arr[j] >= 0:
            swap_element(arr, j, i)
            i--
            j++
        else if arr[j] < 0:
            j++
        else:
            i--

// Example usage
arr = [2, -1, 0, -2, 1, 8, -7, 3, 5, 9, 4, 2, -5, 10, -9]
size = size(arr)
separate_elements(arr, size)
print(arr)

Algorithm Explanation

1. The swap_element function swaps two elements of the array at given indices i and j.
2. The separate_elements function takes the array and its size as parameters.
3. It initializes two pointers, j starting from the beginning (for negative elements) and i starting from the end (for non-negative elements).
4. The function compares the elements at indices i and j:
   • If the element at i is negative and the element at j is non-negative, swap the elements and move i left and j right.
   • If the element at j is negative, move j right.
   • If the element at i is non-negative, move i left.
5. Continue these steps until i crosses j.
6. At this point, the negative elements are at the beginning and the non-negative elements are at the end.

Code Solution

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

// C Program to
// Move all negative elements at the beginning of array
#include <stdio.h>
 //Function which is swapping two array elements of given location
void swap_element(int arr[], int i, int j)
{
	//Get i location element
	int temp = arr[i];
	//set new values
	arr[i] = arr[j];
	arr[j] = temp;
}
//Function which is display array elements
void display(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
//Function which is separating given array elements of Even and odd numbers
void separate_element(int arr[], int size)
{
	int j = 0;
	int i = size - 1;
	//Just before the modifying array elements
	printf("Before Move negative elements \n");
	display(arr, size);
	while (i > j)
	{
		if (arr[i] < 0 && arr[j] >= 0)
		{
			//Swap the array elements
			swap_element(arr, j, i);
			i--;
			j++;
		}
		else if (arr[j] < 0)
		{
			j++;
		}
		else
		{
			i--;
		}
	}
	//After modify array elements
	printf("After move negative elements \n");
	display(arr, size);
	printf("\n");
}
int main()
{
	//Define array elements
	int arr1[] = {
		2,
		-1,
		0,
		-2,
		1,
		8,
		-7,
		3,
		5,
		9,
		4,
		2,
		-5,
		10,
		-9
	};
	int size = sizeof(arr1) / sizeof(arr1[0]);
	separate_element(arr1, size);
	//Define array elements
	int arr2[] = {
		1,
		-1,
		-2,
		4,
		5,
		6,
		-7,
		3
	};
	size = sizeof(arr2) / sizeof(arr2[0]);
	separate_element(arr2, size);
	return 0;
}

Before Move negative elements
2 -1 0 -2 1 8 -7 3 5 9 4 2 -5 10 -9
After move negative elements
-9 -1 -5 -2 -7 8 1 3 5 9 4 2 0 10 2

Before Move negative elements
1 -1 -2 4 5 6 -7 3
After move negative elements
-7 -1 -2 4 5 6 1 3

/*
  Java Program
  Move all negative elements at the beginning of array
*/
class MyArray
{
	//Function which is swapping two array elements of given location
	public void swap_element(int[] arr, int i, int j)
	{
		//Get i location element
		int temp = arr[i];
		//set new values
		arr[i] = arr[j];
		arr[j] = temp;
	}
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + arr[i] + " ");
		}
		System.out.print("\n");
	}
	//Function which is separating given array elements of Even and odd numbers
	public void separate_element(int[] arr, int size)
	{
		int j = 0;
		int i = size - 1;
		//Just before the modifying array elements
		System.out.print("Before Move negative elements \n");
		display(arr, size);
		while (i > j)
		{
			if (arr[i] < 0 && arr[j] >= 0)
			{
				//Swap the array elements
				swap_element(arr, j, i);
				i--;
				j++;
			}
			else if (arr[j] < 0)
			{
				j++;
			}
			else
			{
				i--;
			}
		}
		//After modify array elements
		System.out.print("After move negative elements \n");
		display(arr, size);
		System.out.print("\n");
	}
	public static void main(String[] args)
	{
		MyArray obj = new MyArray();
		//Define array elements
		int[] arr1 = {
			2,
			-1,
			0,
			-2,
			1,
			8,
			-7,
			3,
			5,
			9,
			4,
			2,
			-5,
			10,
			-9
		};
		int size = arr1.length;
		obj.separate_element(arr1, size);
		//Define array elements
		int[] arr2 = {
			1,
			-1,
			-2,
			4,
			5,
			6,
			-7,
			3
		};
		size = arr2.length;
		obj.separate_element(arr2, size);
	}
}

Before Move negative elements
 2  -1  0  -2  1  8  -7  3  5  9  4  2  -5  10  -9
After move negative elements
 -9  -1  -5  -2  -7  8  1  3  5  9  4  2  0  10  2

Before Move negative elements
 1  -1  -2  4  5  6  -7  3
After move negative elements
 -7  -1  -2  4  5  6  1  3

/*
  C++ Program
  Move all negative elements at the beginning of array
*/
#include<iostream>

using namespace std;
class MyArray
{
	public:
		//Function which is swapping two array elements of given location
		void swap_element(int arr[], int i, int j)
		{
			//Get i location element
			int temp = arr[i];
			//set new values
			arr[i] = arr[j];
			arr[j] = temp;
		}
	//Function which is display array elements
	void display(int arr[], int size)
	{
		for (int i = 0; i < size; ++i)
		{
			cout << " " << arr[i] << " ";
		}
		cout << "\n";
	}
	//Function which is separating given array elements of Even and odd numbers
	void separate_element(int arr[], int size)
	{
		int j = 0;
		int i = size - 1;
		cout << "Before Move negative elements \n";
		this->display(arr, size);
		while (i > j)
		{
			if (arr[i] < 0 && arr[j] >= 0)
			{
				//Swap the array elements
				this->swap_element(arr, j, i);
				i--;
				j++;
			}
			else if (arr[j] < 0)
			{
				j++;
			}
			else
			{
				i--;
			}
		}
		cout << "After move negative elements \n";
		this->display(arr, size);
		cout << "\n";
	}
};
int main()
{
	MyArray obj ;
	int arr1[] = {
		2,
		-1,
		0,
		-2,
		1,
		8,
		-7,
		3,
		5,
		9,
		4,
		2,
		-5,
		10,
		-9
	};
	int size = sizeof(arr1) / sizeof(arr1[0]);
	obj.separate_element(arr1, size);
	int arr2[] = {
		1,
		-1,
		-2,
		4,
		5,
		6,
		-7,
		3
	};
	size = sizeof(arr2) / sizeof(arr2[0]);
	obj.separate_element(arr2, size);
	return 0;
}

Before Move negative elements
 2  -1  0  -2  1  8  -7  3  5  9  4  2  -5  10  -9
After move negative elements
 -9  -1  -5  -2  -7  8  1  3  5  9  4  2  0  10  2

Before Move negative elements
 1  -1  -2  4  5  6  -7  3
After move negative elements
 -7  -1  -2  4  5  6  1  3

/*
  C# Program
  Move all negative elements at the beginning of array
*/
using System;
class MyArray
{
	//Function which is swapping two array elements of given location
	public void swap_element(int[] arr, int i, int j)
	{
		//Get i location element
		int temp = arr[i];
		//set new values
		arr[i] = arr[j];
		arr[j] = temp;
	}
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; i++)
		{
			Console.Write(" " + arr[i] + " ");
		}
		Console.Write("\n");
	}
	//Function which is separating given array elements of Even and odd numbers
	public void separate_element(int[] arr, int size)
	{
		int j = 0;
		int i = size - 1;
		Console.Write("Before Move negative elements \n");
		display(arr, size);
		while (i > j)
		{
			if (arr[i] < 0 && arr[j] >= 0)
			{
				//Swap the array elements
				swap_element(arr, j, i);
				i--;
				j++;
			}
			else if (arr[j] < 0)
			{
				j++;
			}
			else
			{
				i--;
			}
		}
		Console.Write("After move negative elements \n");
		display(arr, size);
		Console.Write("\n");
	}
	public static void Main(String[] args)
	{
		MyArray obj = new MyArray();
		int[] arr1 = {
			2,
			-1,
			0,
			-2,
			1,
			8,
			-7,
			3,
			5,
			9,
			4,
			2,
			-5,
			10,
			-9
		};
		int size = arr1.Length;
		obj.separate_element(arr1, size);
		int[] arr2 = {
			1,
			-1,
			-2,
			4,
			5,
			6,
			-7,
			3
		};
		size = arr2.Length;
		obj.separate_element(arr2, size);
	}
}

Before Move negative elements
 2  -1  0  -2  1  8  -7  3  5  9  4  2  -5  10  -9
After move negative elements
 -9  -1  -5  -2  -7  8  1  3  5  9  4  2  0  10  2

Before Move negative elements
 1  -1  -2  4  5  6  -7  3
After move negative elements
 -7  -1  -2  4  5  6  1  3

<?php
/*
  Php Program
  Move all negative elements at the beginning of array
*/
class MyArray
{
	//Function which is swapping two array elements of given location
	function swap_element( & $arr, $i, $j)
	{
		//Get i location element
		$temp = $arr[$i];
		//set new values
		$arr[$i] = $arr[$j];
		$arr[$j] = $temp;
	}
	//Function which is display array elements
	function display( & $arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $arr[$i] ." ";
		}
		echo "\n";
	}
	//Function which is separating given array elements of Even and odd numbers
	function separate_element( & $arr, $size)
	{
		$j = 0;
		$i = $size - 1;
		echo "Before Move negative elements \n";
		$this->display($arr, $size);
		while ($i > $j)
		{
			if ($arr[$i] < 0 && $arr[$j] >= 0)
			{
				//Swap the array elements
				$this->swap_element($arr, $j, $i);
				$i--;
				$j++;
			}
			else if ($arr[$j] < 0)
			{
				$j++;
			}
			else
			{
				$i--;
			}
		}
		echo "After move negative elements \n";
		$this->display($arr, $size);
		echo "\n";
	}
}

function main()
{
	$obj = new MyArray();
	//Define array elements
	$arr1 = array(2, -1, 0, -2, 1, 8, -7, 3, 5, 9, 4, 2, -5, 10, -9);
	$size = count($arr1);
	$obj->separate_element($arr1, $size);
	//Define array elements
	$arr2 = array(1, -1, -2, 4, 5, 6, -7, 3);
	$size = count($arr2);
	$obj->separate_element($arr2, $size);
}
main();

Before Move negative elements
 2  -1  0  -2  1  8  -7  3  5  9  4  2  -5  10  -9
After move negative elements
 -9  -1  -5  -2  -7  8  1  3  5  9  4  2  0  10  2

Before Move negative elements
 1  -1  -2  4  5  6  -7  3
After move negative elements
 -7  -1  -2  4  5  6  1  3

/*
  Node Js Program
  Move all negative elements at the beginning of array
*/
class MyArray
{
	//Function which is swapping two array elements of given location
	swap_element(arr, i, j)
	{
		//Get i location element
		var temp = arr[i];
		//set new values
		arr[i] = arr[j];
		arr[j] = temp;
	}
	//Function which is display array elements
	display(arr, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i] + " ");
		}
		process.stdout.write("\n");
	}
	//Function which is separating given array elements of Even and odd numbers
	separate_element(arr, size)
	{
		var j = 0;
		var i = size - 1;
		process.stdout.write("Before Move negative elements \n");
		this.display(arr, size);
		while (i > j)
		{
			if (arr[i] < 0 && arr[j] >= 0)
			{
				//Swap the array elements
				this.swap_element(arr, j, i);
				i--;
				j++;
			}
			else if (arr[j] < 0)
			{
				j++;
			}
			else
			{
				i--;
			}
		}
		process.stdout.write("After move negative elements \n");
		this.display(arr, size);
		process.stdout.write("\n");
	}
}

function main()
{
	var obj = new MyArray();
	//Define array elements
	var arr1 = [2, -1, 0, -2, 1, 8, -7, 3, 5, 9, 4, 2, -5, 10, -9];
	var size = arr1.length;
	obj.separate_element(arr1, size);
	//Define array elements
	var arr2 = [1, -1, -2, 4, 5, 6, -7, 3];
	size = arr2.length;
	obj.separate_element(arr2, size);
}
main();

Before Move negative elements
 2  -1  0  -2  1  8  -7  3  5  9  4  2  -5  10  -9
After move negative elements
 -9  -1  -5  -2  -7  8  1  3  5  9  4  2  0  10  2

Before Move negative elements
 1  -1  -2  4  5  6  -7  3
After move negative elements
 -7  -1  -2  4  5  6  1  3

#   Python 3 Program
#   Move all negative elements at the beginning of array

class MyArray :
	# Function which is swapping two array elements of given location
	def swap_element(self, arr, i, j) :
		# Get i location element
		temp = arr[i]
		# set new values
		arr[i] = arr[j]
		arr[j] = temp
	
	# Function which is display array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i] ," ", end = "")
			i += 1
		
		print("\n", end = "")
	
	# Function which is separating given array elements of Even and odd numbers
	def separate_element(self, arr, size) :
		j = 0
		i = size - 1
		print("Before Move negative elements \n", end = "")
		self.display(arr, size)
		while (i > j) :
			if (arr[i] < 0 and arr[j] >= 0) :
				# Swap the array elements
				self.swap_element(arr, j, i)
				i -= 1
				j += 1
			
			elif(arr[j] < 0) :
				j += 1
			else :
				i -= 1
			
		
		print("After move negative elements \n", end = "")
		self.display(arr, size)
		print("\n", end = "")
	

def main() :
	obj = MyArray()
	# Define array elements
	arr1 = [2, -1, 0, -2, 1, 8, -7, 3, 5, 9, 4, 2, -5, 10, -9]
	size = len(arr1)
	obj.separate_element(arr1, size)
	# Define array elements
	arr2 = [1, -1, -2, 4, 5, 6, -7, 3]
	size = len(arr2)
	obj.separate_element(arr2, size)

if __name__ == "__main__": main()

Before Move negative elements
  2    -1    0    -2    1    8    -7    3    5    9    4    2    -5    10    -9
After move negative elements
  -9    -1    -5    -2    -7    8    1    3    5    9    4    2    0    10    2

Before Move negative elements
  1    -1    -2    4    5    6    -7    3
After move negative elements
  -7    -1    -2    4    5    6    1    3

#   Ruby Program
#   Move all negative elements at the beginning of array

class MyArray

	# Function which is swapping two array elements of given location
	def swap_element(arr, i, j)
	
		# Get i location element
		temp = arr[i]
		# set new values
		arr[i] = arr[j]
		arr[j] = temp
	end
	# Function which is display array elements
	def display(arr, size)
	
		i = 0
		while (i < size)
		
			print(" ", arr[i] ," ")
			i += 1
		end
		print("\n")
	end
	# Function which is separating given array elements of Even and odd numbers
	def separate_element(arr, size)
	
		j = 0
		i = size - 1
		# Just before the modifying array elements
		print("Before Move negative elements \n")
		self.display(arr, size)
		while (i > j)
		
			if (arr[i] < 0 && arr[j] >= 0)
			
				# Swap the array elements
				self.swap_element(arr, j, i)
				i -= 1
				j += 1
			elsif(arr[j] < 0)
			
				j += 1
			else
			
				i -= 1
			end
		end
		# After modify array elements
		print("After move negative elements \n")
		self.display(arr, size)
		print("\n")
	end
end
def main()

	obj = MyArray.new()
	# Define array elements
	arr1 = [2, -1, 0, -2, 1, 8, -7, 3, 5, 9, 4, 2, -5, 10, -9]
	size = arr1.length
	obj.separate_element(arr1, size)
	# Define array elements
	arr2 = [1, -1, -2, 4, 5, 6, -7, 3]
	size = arr2.length
	obj.separate_element(arr2, size)
end
main()

Before Move negative elements 
 2  -1  0  -2  1  8  -7  3  5  9  4  2  -5  10  -9 
After move negative elements 
 -9  -1  -5  -2  -7  8  1  3  5  9  4  2  0  10  2 

Before Move negative elements 
 1  -1  -2  4  5  6  -7  3 
After move negative elements 
 -7  -1  -2  4  5  6  1  3 

/*
  Scala Program
  Move all negative elements at the beginning of array
*/
class MyArray
{
	//Function which is swapping two array elements of given location
	def swap_element(arr: Array[Int], i: Int, j: Int): Unit = {
		//Get i location element
		var temp: Int = arr(i);
		//set new values
		arr(i) = arr(j);
		arr(j) = temp;
	}
	//Function which is display array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i) + " ");
			i += 1;
		}
		print("\n");
	}
	//Function which is separating given array elements of Even and odd numbers
	def separate_element(arr: Array[Int], size: Int): Unit = {
		var j: Int = 0;
		var i: Int = size - 1;
		//Just before the modifying array elements
		print("Before Move negative elements \n");
		display(arr, size);
		while (i > j)
		{
			if (arr(i) < 0 && arr(j) >= 0)
			{
				//Swap the array elements
				swap_element(arr, j, i);
				i -= 1;
				j += 1;
			}
			else if (arr(j) < 0)
			{
				j += 1;
			}
			else
			{
				i -= 1;
			}
		}
		//After modify array elements
		print("After move negative elements \n");
		display(arr, size);
		print("\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyArray = new MyArray();
		//Define array elements
		var arr1: Array[Int] = Array(2, -1, 0, -2, 1, 8, -7, 3, 5, 9, 4, 2, -5, 10, -9);
		var size: Int = arr1.length;
		obj.separate_element(arr1, size);
		//Define array elements
		var arr2: Array[Int] = Array(1, -1, -2, 4, 5, 6, -7, 3);
		size = arr2.length;
		obj.separate_element(arr2, size);
	}
}

Before Move negative elements
 2  -1  0  -2  1  8  -7  3  5  9  4  2  -5  10  -9
After move negative elements
 -9  -1  -5  -2  -7  8  1  3  5  9  4  2  0  10  2

Before Move negative elements
 1  -1  -2  4  5  6  -7  3
After move negative elements
 -7  -1  -2  4  5  6  1  3

/*
  Swift Program
  Move all negative elements at the beginning of array
*/
class MyArray
{
	//Function which is swapping two array elements of given location
	func swap_element(_ arr: inout[Int], _ i: Int, _ j: Int)
	{
		//Get i location element
		let temp: Int = arr[i];
		//set new values
		arr[i] = arr[j];
		arr[j] = temp;
	}
	//Function which is display array elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i] ," ", terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	//Function which is separating given array elements of Even and odd numbers
	func separate_element(_ arr: inout[Int], _ size: Int)
	{
		var j: Int = 0;
		var i: Int = size - 1;
		print("Before Move negative elements \n", terminator: "");
		self.display(arr, size);
		while (i > j)
		{
			if (arr[i] < 0 && arr[j] >= 0)
			{
				//Swap the array elements
				self.swap_element(&arr, j, i);
				i -= 1;
				j += 1;
			}
			else if (arr[j] < 0)
			{
				j += 1;
			}
			else
			{
				i -= 1;
			}
		}
		print("After move negative elements \n", terminator: "");
		self.display(arr, size);
		print("\n", terminator: "");
	}
}
func main()
{
	let obj: MyArray = MyArray();
	//Define array elements
	var arr1: [Int] = [2, -1, 0, -2, 1, 8, -7, 3, 5, 9, 4, 2, -5, 10, -9];
	var size: Int = arr1.count;
	obj.separate_element(&arr1, size);
	//Define array elements
	var arr2: [Int] = [1, -1, -2, 4, 5, 6, -7, 3];
	size = arr2.count;
	obj.separate_element(&arr2, size);
}
main();

Before Move negative elements
  2    -1    0    -2    1    8    -7    3    5    9    4    2    -5    10    -9
After move negative elements
  -9    -1    -5    -2    -7    8    1    3    5    9    4    2    0    10    2

Before Move negative elements
  1    -1    -2    4    5    6    -7    3
After move negative elements
  -7    -1    -2    4    5    6    1    3

Time Complexity

The algorithm runs in O(n) time, where n is the size of the array. The two pointers traverse through the array in opposite directions, ensuring each element is visited only once.