Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation
3.
Solution
3.1.
Idea
3.2.
Algorithm
3.3.
Visualisation
3.4.
Implementation
3.5.
C++
3.6.
Java
3.7.
Python
3.8.
JavaScript
3.9.
C#
3.10.
Output
3.11.
Complexity Analysis
4.
Frequently Asked Questions 
4.1.
How do I move all the negative elements to one side of the array?
4.2.
Can negative elements be placed in an array?
4.3.
How to remove negative elements from an array?
4.4.
What do you mean by “constant extra space” in a problem?
4.5.
What do you mean by the pivot in data structure?
5.
Conclusion
Last Updated: May 26, 2024
Easy

Move All Negative Elements to the End in Order With Extra Space Allowed

Author Aniket Majhi
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In programming, managing and manipulating arrays is a fundamental skill that can solve a myriad of problems efficiently. One common task that arises is the need to reorder an array such that all negative elements are moved to the end while maintaining the relative order of positive elements and zeros. This can be particularly useful in scenarios like data processing, sorting algorithms, or simply optimizing the structure of data for better performance in subsequent operations.

Move All Negative Elements to the End in Order With Extra Space Allowed

Also see, Morris Traversal for Inorder and  Rabin Karp Algorithm

Problem Statement

You are given an array of positive and negative numbers. You need to move all the negative numbers to the end of the array by keeping the order of the positive and negative elements the same as given in the original array.

Example

Let’s understand the above problem with an example.

Input

{1,-2,4,-6,-3,9}

Output

{1,4,9,-2,-6,-3}

Explanation

The given array is {1,-2,4,-6,-3,9}

The rearrangement should follow like below.

As you can see, negative numbers are moved to the end of the array by keeping their order the same.

We hope the problem statement is clear to you now. Let’s move to the solution part.

Also See, Array Implementation of Queue

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;

}

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] + " ");
}
}
}

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)

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);

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 problemRearranging 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 ArrayMultiple Left Rotation in an Array in O(1)Next Greater and Smaller Element for Every Element in an ArrayUnderstanding Insertion Sort, Understanding Quick SortMerge 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!

Previous article
Form Minimum Number from Given Sequence
Next article
Making elements of two arrays identical with minimum increment/decrement
Live masterclass