Home » Technical Interview Questions » Array Interview Questions » Move all Negative Numbers to Beginning and Positive to End with Constant Extra Space

Move all Negative Numbers to Beginning and Positive to End with Constant Extra Space




Difficulty Level Easy

Suppose you have an array of integers. It consists of both negative and positive numbers and the problem statement asks to shift/move all the negative and positive elements to the left of the array and to the right of the array respectively without using extra space.

Example

 Input:

arr[]={2,4,-10,13,-7,-60,52,8,-19 }

Output:

-10 -7 -60 -19 4 2 52 8 13

Explanation:

Since all the numbers are shifted towards left and all the positive number is shifted towards right.

Move all Negative Numbers to Beginning and Positive to End with Constant Extra Space

Algorithm

  1. Set the j to 0.
  2. Traversing the array from 0 to n(exclusively, where n is array’s length).
    1. Check if any element of an array is less than the 0,
      1. Check if i should not be equal to j,
        1. Swap the values of indexes arr[i] and arr[j], and increase the value of j.
  3. Print the array.

Explanation for Move all Negative Numbers to Beginning and Positive to End

We are given an array of integer, and the array is containing the positive and negative elements. We have asked to shift all the negative elements to the left and the positive numbers to the right. For this, we are going to swap all the numbers, which are positive and negative elements. Traverse the array first and then check for the negative numbers, if the number is negative then only we will go for swapping the values.

READ  Merge Overlapping Intervals

Set the value of j to 0, it will be used for the alternative value to swap with. We will start traversing the array and check for each number as arr[i] is less than 0, if it is less than 0, means we found the negative number, and therefore we will check for if both of the indexes are not same, is all of the above conditions are true, then we will swap the numbers as arr[i] and arr[j] will be swapped, and increase the value of j. we will keep that traversal going on till all the possible values have been traversed and swapped and rearranged according to the given condition.

We have checked that condition that arr[i] is less than 0 because we are just arranging the negative numbers, all negative numbers after swapping will be arranged to the left of the array, and all other positive numbers will be arranged automatically to the right of the array. After all the swapping we have done, we just need to print the array in which the swapping operations performed.

Implementation

C++ program for Move all Negative Numbers to Beginning and Positive to End

#include<iostream>

using namespace std;

void shiftIntegers(int arr[], int n)
{
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] < 0)
        {
            if (i != j)
                swap(arr[i], arr[j]);
            j++;
        }
    }
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
}
int main()
{
    int arr[] = { 2,4,-10,13,-7,-60,52,8,-19 };
    int n = sizeof(arr) / sizeof(arr[0]);
    shiftIntegers(arr, n);

    return 0;
}
-10 -7 -60 -19 4 2 52 8 13

Java program for Move all Negative Numbers to Beginning and Positive to End

class rearrangeNegativePositive
{
    public static void shiftIntegers(int arr[], int n)
    {
        int j = 0, temp;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] < 0)
            {
                if (i != j)
                {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                j++;
            }
        }
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
    public static void main(String args[])
    {
        int arr[] = { 2,4,-10,13,-7,-60,52,8,-19 };
        int n = arr.length;

        shiftIntegers(arr, n);
        printArray(arr, n);
    }
}
-10 -7 -60 -19 4 2 52 8 13

Complexity Analysis for Move all Negative Numbers to Beginning and Positive to End

Time Complexity

O(n) where “n” is the number of elements in the array.

READ  Three way partitioning of an array around a given range

Space Complexity

O(1) as no extra space is required.

Reference

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup