Solution
The solution to the above problem is shown below step by step:
Idea
As we can use extra spaces, the simple idea is to use an empty array to store all positive elements first, then all the negative elements in order. After that, copy all the elements from the array to the original array.
Algorithm
- Create an empty array.
- Traverse through the original array. Find positive elements and store them in the new array in order.
- Again Traverse through the original array. Find negative elements and store them in the new array in order starting after the last positive element.
- Finally, copy all the new array elements into the original array.
Visualisation
The visualisation of the above algorithm is shown below. Here we have used the sample test case.
Implementation
- C++
- Java
- Python
- JavaScript
- C#
C++
#include<bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, -2, 4, -6, -3, 9};
// size of the array
int n = sizeof(arr) / sizeof(arr[0]);
// new created empty array
int new_arr[n];
// array pointer
int p = 0;
// traverse the original array to store all positive number first to the newly created array
for(int i = 0; i < n; i++) {
if(arr[i] > 0) {
new_arr[p] = arr[i];
p++;
}
}
// then traverse the original array to store all negative numbers to the newly created array
for(int i = 0 ; i < n ; i++){
if(arr[i] < 0) {
new_arr[p] = arr[i];
p++;
}
}
// now copy the elements of the newly created array to the original array
for(int i = 0; i < n ; i++) {
arr[i] = new_arr[i];
}
// print the original array
cout << "The elements of the original array are: ";
for(int i =0 ; i < n ; i++) {
cout << arr[i] <<" ";
}
return 0;
}
You can also try this code with Online C++ Compiler
Java
public class MoveNegativeElements {
public static void main(String[] args) {
int[] arr = {1, -2, 4, -6, -3, 9};
int n = arr.length;
int[] newArr = new int[n];
int p = 0;
// Store positive numbers first
for (int i = 0; i < n; i++) {
if (arr[i] > 0) {
newArr[p] = arr[i];
p++;
}
}
// Store negative numbers
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
newArr[p] = arr[i];
p++;
}
}
// Copy back to original array
for (int i = 0; i < n; i++) {
arr[i] = newArr[i];
}
// Print the original array
System.out.print("The elements of the original array are: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
You can also try this code with Online Java Compiler
Python
def move_negatives(arr):
n = len(arr)
new_arr = [0] * n
p = 0
# Store positive numbers first
for i in range(n):
if arr[i] > 0:
new_arr[p] = arr[i]
p += 1
# Store negative numbers
for i in range(n):
if arr[i] < 0:
new_arr[p] = arr[i]
p += 1
# Copy back to original array
for i in range(n):
arr[i] = new_arr[i]
# Print the original array
print("The elements of the original array are:", arr)
arr = [1, -2, 4, -6, -3, 9]
move_negatives(arr)
You can also try this code with Online Python Compiler
JavaScript
function moveNegatives(arr) {
let n = arr.length;
let newArr = new Array(n);
let p = 0;
// Store positive numbers first
for (let i = 0; i < n; i++) {
if (arr[i] > 0) {
newArr[p] = arr[i];
p++;
}
}
// Store negative numbers
for (let i = 0; i < n; i++) {
if (arr[i] < 0) {
newArr[p] = arr[i];
p++;
}
}
// Copy back to original array
for (let i = 0; i < n; i++) {
arr[i] = newArr[i];
}
// Print the original array
console.log("The elements of the original array are:", arr);
}
let arr = [1, -2, 4, -6, -3, 9];
moveNegatives(arr);
You can also try this code with Online Javascript Compiler
C#
using System;
class MoveNegativeElements {
static void Main() {
int[] arr = {1, -2, 4, -6, -3, 9};
int n = arr.Length;
int[] newArr = new int[n];
int p = 0;
// Store positive numbers first
for (int i = 0; i < n; i++) {
if (arr[i] > 0) {
newArr[p] = arr[i];
p++;
}
}
// Store negative numbers
for (int i = 0; i < n; i++) {
if (arr[i] < 0) {
newArr[p] = arr[i];
p++;
}
}
// Copy back to original array
for (int i = 0; i < n; i++) {
arr[i] = newArr[i];
}
// Print the original array
Console.Write("The elements of the original array are: ");
for (int i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
}
Output
Complexity Analysis
The time and space complexity are shown below,
Time complexity: O(n)
Space Complexity: O(n)
Follow these articles to learn about the constant extra space approaches to the problem, Rearranging Positive and Negative Numbers With Constant Extra Space | Part 1 and Rearranging Positive and Negative Numbers With Constant Extra Space | Part 2.
Frequently Asked Questions
How do I move all the negative elements to one side of the array?
Traverse the array, store positive elements in a new array first, followed by negative elements, then copy back to the original array.
Can negative elements be placed in an array?
Yes, negative elements can be placed in an array just like positive elements and zeros, depending on the data type of the array.
How to remove negative elements from an array?
Filter the array to include only non-negative elements, creating a new array without any negative values.
What do you mean by “constant extra space” in a problem?
The space(memory allocation) you have taken to solve the problem doesn’t depend on the input variable.
What do you mean by the pivot in data structure?
The pivot element in a data structure is the element that is selected first by an algorithm to solve the problem.
Conclusion
This article extensively discussed moving all the negative elements to the end of the array with extra space allowed.
We started with the basic introduction. We discussed,
- Problem Statement
- Solution
- We discussed the idea first.
- Visualisation of the idea with an example
- Implementation of our idea
- Finally, we analyse the complexity of the algorithm.
We hope this blog has helped you enhance your knowledge regarding moving all the negative elements to the end of the array in order with extra space allowed. And if you would like to learn more, check out our articles on Find the Minimum Element in a Rotated Sorted Array, Multiple Left Rotation in an Array in O(1), Next Greater and Smaller Element for Every Element in an Array, Understanding Insertion Sort, Understanding Quick Sort, Merge Sort. Do upvote our blog to help other ninjas grow.
Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations and much more.!
Happy Reading!
116+ registered 