# Move all negative elements to end in order with extra space allowed

Given an unsorted array of both negative and positive integer. The task is place all negative element at the end of array without changing the order of positive element and negative element.

Examples:

```Input : arr[] = {1, -1, 3, 2, -7, -5, 11, 6 }
Output : 1  3  2  11  6  -1  -7  -5

Input : arr[] = {-5, 7, -3, -4, 9, 10, -1, 11}
Output : 7  9  10  11  -5  -3  -4  -1
```

We have discussed different approaches to this problem in below post.

Rearrange positive and negative numbers with constant extra space

The problem becomes easier if we are allowed to use extra space. Idea is create an empty array (temp[]). First we store all positive element of given array and then we store all negative element of array in Temp[]. Finally we copy temp[] to original array.

Below is the implementation of above idea:

## C/C++

 `// C++ program to Move All -ve Element At End ` `// Without changing order Of Array Element ` `#include ` `using` `namespace` `std; ` ` `  `// Moves all -ve element to end of array in ` `// same order. ` `void` `segregateElements(``int` `arr[], ``int` `n) ` `{ ` `    ``// Create an empty array to store result ` `    ``int` `temp[n]; ` ` `  `    ``// Traversal array and store +ve element in ` `    ``// temp array ` `    ``int` `j = 0; ``// index of temp ` `    ``for` `(``int` `i = 0; i < n ; i++) ` `        ``if` `(arr[i] >= 0 ) ` `            ``temp[j++] = arr[i]; ` ` `  `    ``// If array contains all positive or all negative. ` `    ``if` `(j == n || j == 0) ` `        ``return``; ` ` `  `    ``// Store -ve element in temp array ` `    ``for` `(``int` `i = 0 ; i < n ; i++) ` `        ``if` `(arr[i] < 0) ` `            ``temp[j++] = arr[i]; ` ` `  `    ``// Copy contents of temp[] to arr[] ` `    ``memcpy``(arr, temp, ``sizeof``(temp)); ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``int` `arr[] = {1 ,-1 ,-3 , -2, 7, 5, 11, 6 }; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]); ` ` `  `    ``segregateElements(arr, n); ` ` `  `    ``for` `(``int` `i = 0; i < n; i++) ` `       ``cout << arr[i] << ``" "``; ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to Move All -ve Element At End ` `// Without changing order Of Array Element ` `import` `java.util.Arrays; ` ` `  `class` `GFG { ` `     `  `    ``// Moves all -ve element to end of array in ` `    ``// same order. ` `    ``static` `void` `segregateElements(``int` `arr[], ``int` `n) ` `    ``{ ` `         `  `        ``// Create an empty array to store result ` `        ``int` `temp[] = ``new` `int``[n]; ` ` `  `        ``// Traversal array and store +ve element in ` `        ``// temp array ` `        ``int` `j = ``0``; ``// index of temp ` `         `  `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``if` `(arr[i] >= ``0``) ` `                ``temp[j++] = arr[i]; ` ` `  `        ``// If array contains all positive or all  ` `        ``// negative. ` `        ``if` `(j == n || j == ``0``) ` `            ``return``; ` ` `  `        ``// Store -ve element in temp array ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``if` `(arr[i] < ``0``) ` `                ``temp[j++] = arr[i]; ` ` `  `        ``// Copy contents of temp[] to arr[] ` `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``arr[i] = temp[i]; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main(String arg[]) ` `    ``{ ` `        ``int` `arr[] = { ``1``, -``1``, -``3``, -``2``, ``7``, ``5``, ``11``, ``6` `}; ` `        ``int` `n = arr.length; ` ` `  `        ``segregateElements(arr, n); ` ` `  `        ``for` `(``int` `i = ``0``; i < n; i++) ` `            ``System.out.print(arr[i] + ``" "``); ` `    ``} ` `} ` ` `  `// This code is contributed by Anant Agarwal. `

## Python

 `# Python program to Move All -ve Element At End ` `# Without changing order Of Array Element ` `  `  `# Moves all -ve element to end of array in ` `# same order. ` `def` `segregateElements(arr, n): ` `    ``# Create an empty array to store result ` `    ``temp ``=` `[``0` `for` `k ``in` `range``(n)] ` `  `  `    ``# Traversal array and store +ve element in ` `    ``# temp array ` `    ``j ``=` `0` `# index of temp ` `    ``for` `i ``in` `range``(n): ` `        ``if` `(arr[i] >``=` `0` `): ` `            ``temp[j] ``=` `arr[i] ` `            ``j ``+``=``1` `  `  `    ``# If array contains all positive or all negative. ` `    ``if` `(j ``=``=` `n ``or` `j ``=``=` `0``): ` `        ``return` `  `  `    ``# Store -ve element in temp array ` `    ``for` `i ``in` `range``(n): ` `        ``if` `(arr[i] < ``0``): ` `            ``temp[j] ``=` `arr[i] ` `            ``j ``+``=``1` `  `  `    ``# Copy contents of temp[] to arr[] ` `    ``for` `k ``in` `range``(n): ` `        ``arr[k] ``=` `temp[k] ` ` `  `# Driver program ` `arr ``=` `[``1` `,``-``1` `,``-``3` `, ``-``2``, ``7``, ``5``, ``11``, ``6` `] ` `n ``=` `len``(arr) ` ` `  `segregateElements(arr, n); ` `  `  `for` `i ``in` `range``(n): ` `    ``print` `arr[i], ` ` `  `# Contributed by Afzal aka Saan `

## C#

 `// C# program to Move All -ve Element At End ` `// Without changing order Of Array Element ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Moves all -ve element to  ` `    ``// end of array in same order. ` `    ``static` `void` `segregateElements(``int``[] arr, ``int` `n) ` `    ``{ ` `        ``// Create an empty array to store result ` `        ``int``[] temp = ``new` `int``[n]; ` ` `  `        ``// Traversal array and store +ve element in ` `        ``// temp array ` `        ``int` `j = 0; ``// index of temp ` ` `  `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``if` `(arr[i] >= 0) ` `                ``temp[j++] = arr[i]; ` ` `  `        ``// If array contains all positive or all ` `        ``// negative. ` `        ``if` `(j == n || j == 0) ` `            ``return``; ` ` `  `        ``// Store -ve element in temp array ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``if` `(arr[i] < 0) ` `                ``temp[j++] = arr[i]; ` ` `  `        ``// Copy contents of temp[] to arr[] ` `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``arr[i] = temp[i]; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int``[] arr = { 1, -1, -3, -2, 7, 5, 11, 6 }; ` `        ``int` `n = arr.Length; ` `        ``segregateElements(arr, n); ` ` `  `        ``for` `(``int` `i = 0; i < n; i++) ` `            ``Console.Write(arr[i] + ``" "``); ` `    ``} ` `} ` ` `  `// This Code is contributed by vt_m. `

## PHP

 `= 0 ) ` `            ``\$temp``[``\$j``++] = ``\$arr``[``\$i``]; ` ` `  `    ``// If array contains all positive  ` `    ``// or all negative. ` `    ``if` `(``\$j` `== ``\$n` `|| ``\$j` `== 0) ` `        ``return``; ` ` `  `    ``// Store -ve element in temp array ` `    ``for` `(``\$i` `= 0 ; ``\$i` `< ``\$n` `; ``\$i``++) ` `        ``if` `(``\$arr``[``\$i``] < 0) ` `            ``\$temp``[``\$j``++] = ``\$arr``[``\$i``]; ` ` `  `    ``// Copy contents of temp[] to arr[] ` `    ``for``(``\$i` `= 0; ``\$i` `< ``\$n``; ``\$i``++) ` `        ``\$arr``[``\$i``] = ``\$temp``[``\$i``]; ` `} ` ` `  `// Driver Code ` `\$arr` `= ``array``(1 ,-1 ,-3 , -2, 7, 5, 11, 6 ); ` `\$n` `= sizeof(``\$arr``); ` ` `  `segregateElements(``\$arr``, ``\$n``); ` ` `  `for` `(``\$i` `= 0; ``\$i` `< ``\$n``; ``\$i``++) ` `echo` `\$arr``[``\$i``] .``" "``; ` ` `  `// This code is contributed  ` `// by ChitraNayal ` `?> `

Output:

```1 7 5 11 6 -1 -3 -2
```

Time Complexity : O(n)
Auxiliary space : O(n)

## tags:

Arrays array-rearrange Arrays