Move All Negative Numbers To Beginning And Positive To End
You are given an array 'ARR' consisting of 'N' integers. You need to rearrange the array elements such that all negative numbers appear before all positive numbers.

Follow Up:

Can you solve this in O(1) auxiliary space?

Note:

The order of elements in the resulting array is not important.

Example:

Let the array be [1, 2, -3, 4, -4, -5]. On rearranging the array such that all negative numbers appear before all positive numbers we get the resulting array [-3, -5, -4, 2, 4, 1].

Input format:

The very first line of input contains an integer ‘T’ denoting the number of test cases. The first line of every test case contains an integer ‘N’ denoting the number of elements present in the array. The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.

Output format:

For each test case, “Yes” is printed if the resulting array is correct otherwise “No”. Output for each test case is printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just return the resulting array.

Constraints:

1

Question

Move All Negative Numbers To Beginning And Positive To End

You are given an array 'ARR' consisting of 'N' integers. You need to rearrange the array elements such that all negative numbers appear before all positive numbers.

Follow Up:

Can you solve this in O(1) auxiliary space?

Note:

The order of elements in the resulting array is not important.

Example:

Let the array be [1, 2, -3, 4, -4, -5]. On rearranging the array such that all negative numbers appear before all positive numbers we get the resulting array [-3, -5, -4, 2, 4, 1].

Input format:

The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains an integer ‘N’ denoting the number of elements present in the array.

The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.

Output format:

For each test case, “Yes” is printed if the resulting array is correct otherwise “No”.

Output for each test case is printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just return the resulting array.

Constraints:

1 <= T <= 10
1 <= N <= 5 * 10^4
-10^5 <= ARR[i] <= 10^5

Where  ‘T’ represents the number of test cases and ‘N’ represents the number of elements present in the array.

Time Limit: 1 sec

Accepted Answer

The naive approach would be to use an auxiliary array. Copy all elements to that array. Copy all negative elements first to the original array and then all positive elements. This approach would have a time complexity of O(N) but also uses O(N) auxiliary space.
For constant space, we first count total negative numbers.
Then till all negative numbers are moved to the beginning, traverse the array. Swap the positions of negative and positive elements and move negative numbers one by one to correct position.

Accepted Answer

Using Sorting

Approach: A brute force approach could be to just sort the given array in ascending order. This will result in all negative numbers to appear at the beginning and positive number at the end.

Space Complexity: O(1)Explanation:

O(1)

Because no extra space is required.

Time Complexity: O(nlogn)Explanation:

O(N*logN), where N is the number of elements in the array.

In the worst case, sorting requires O(N*logN) time. Hence, the overall complexity is O(N*logN).

C++ (g++ 5.4)

/*

	Time complexity: O(N * logN)

	Space Complexity: O(1)

	

	Where N is the number of elements in the array.

*/



#include 



vector < int > separateNegativeAndPositive(vector < int > & nums) {

	

    // Sort the given array in ascending order.

    sort(nums.begin(), nums.end());



    return nums;

}

Python (3.5)

'''
    Time complexity: O(N * logN)
	Space Complexity: O(1)
	
	Where N is the number of elements in the array.
'''

def separateNegativeAndPositive(nums):
    
    # Sort the given array in ascending order.
    nums.sort()
    return nums

Java (SE 1.8)

/*
    Time complexity: O(N * logN)
    Space Complexity: O(1)
    
    Where N is the number of elements in the array.
*/

import java.util.*;

public class Solution {
    public static ArrayList separateNegativeAndPositive(ArrayList nums) {
        
        // Sort the given array in ascending order.
        Collections.sort(nums);

        return nums;
    }
}

Accepted Answer

Partitioning The Array Into Two Parts

Approach: A better approach could be to use the concept similar to the partitioning algorithm of quicksort. The idea is to start from the leftmost element in the array and keep track of any negative elements. While traversing the array if we find a negative element, we swap the current element with the leftmost positive element. Otherwise, ignore the current element.

The Algorithm is as follows:

Let ‘j’ point to the leftmost positive element in the array. Initially, we set ‘j’ to point to the first element.
Iterate over the array:
- Let ‘i’ be the index of the current element.
- If the current element is negative:
  - If ‘i’ not equal to ‘j’, then swap the ith and jth elements.
  - Increment ‘j’ by 1.
Return the resulting array.

Space Complexity: O(1)Explanation:

O(1)

Because no extra space is required.

Time Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

We are iterating over the array once which requires O(N) time and swapping of elements requires O(1) time. Hence, the overall complexity is O(N).

Java (SE 1.8)

/*
    Time complexity: O(N)
    Space Complexity: O(1)
    
    Where N is the number of elements in the array.
*/

import java.util.ArrayList;

public class Solution {
    public static ArrayList < Integer > separateNegativeAndPositive(ArrayList < Integer > nums) {

        // 'j' stores the index of the leftmost positive element.
        int j = 0;

        for (int i = 0; i < nums.size(); i++) {

            if (nums.get(i) < 0) {

                // Current element is negative.
                if (i != j) {

                    // Swap the current element with the leftmost positive element.
                    int temp = nums.get(i);
                    nums.set(i, nums.get(j));
                    nums.set(j, temp);
                }

                ++j;
            }
        }

        return nums;
    }
}

C++ (g++ 5.4)

/*

	Time complexity: O(N)

	Space Complexity: O(1)

	

	Where N is the number of elements in the array.

*/



vector < int > separateNegativeAndPositive(vector < int > & nums) {



    // 'j' stores the index of the leftmost positive element.

    int j = 0;



    for (int i = 0; i < nums.size(); i++) {



        if (nums[i] < 0) {



            // Current element is negative.

            if (i != j) {



                // Swap the current element with the leftmost positive element.

                swap(nums[i], nums[j]);

            }



            ++j;

        }

    }



    return nums;

}

Python (3.5)

'''
    Time complexity: O(N)
	Space Complexity: O(1)
	
	Where N is the number of elements in the array.
'''

def separateNegativeAndPositive(nums):

    # 'j' stores the index of the leftmost positive element.
    j = 0

    for i in range(len(nums)):

        if (nums[i] < 0):

            # Current element is negative.
            if(i != j):
                
                # Swap the current element with the leftmost positive element.
                get = nums[i], nums[j]
                nums[j], nums[i] = get

            j += 1

    return nums

Accepted Answer

Using Two Pointers

Approach: A simple approach could be to use the concept of a two-pointer. In this approach keep two pointers ‘LEFT’ and ‘RIGHT’ which initially point to the first and the last elements of the array. All the elements to the left of ‘LEFT’ pointer are negative and to the right of ‘RIGHT’ pointer are positive. The idea is to iterate over the array and segregate the positive and negative elements with the help of these pointers.

The Algorithm is as follows:

Create two pointers named ‘LEFT’ and ‘RIGHT’ and initialize them with the first and the last index of the array.
Now, iterate over the array until the ‘LEFT’ is less than ‘RIGHT’:
- While iterating, the following cases may arise.
- Case 1: If both ‘LEFT’ and ‘RIGHT’ pointers point to negative elements, then simply increment the left pointer.
- Case 2: If both ‘LEFT’ and ‘RIGHT’ pointers point to positive elements, then simply decrement the right pointer.
- Case 3: If the ‘LEFT’ pointer points to positive element and ‘RIGHT’ pointer points to negative element, then swap the two elements and increment the left pointer and decrement the right pointer.
- Case 4: Otherwise the ‘LEFT’ pointer points to the negative element and ‘RIGHT’ pointer points to the positive element, then we increment the left pointer and decrement the right pointer.
Return the resulting array.

Space Complexity: O(1)Explanation:

O(1)

Because no extra space is required.

Time Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

We are iterating over the array once which requires O(N) time and swapping of elements requires O(1) time. Hence, the overall complexity is O(N).

Java (SE 1.8)

/*
    Time complexity: O(N)
    Space Complexity: O(1)
    
    Where N is the number of elements in the array.
*/

import java.util.ArrayList;

public class Solution {
    public static ArrayList separateNegativeAndPositive(ArrayList nums) {
        
        // Create two pointers- "LEFT" and "RIGHT".
        int left = 0;
        int right = nums.size() - 1;

        while (left < right) {

            if (nums.get(left) < 0 && nums.get(right) < 0) {

                // Case 1: Both the pointers point to negative elements.
                ++left;
            } 
            else if (nums.get(left) >= 0 && nums.get(right) >= 0) {
                
                // Case 2: Both the pointers point to positive elements.
                --right;
            } 
            else if (nums.get(left) >= 0 && nums.get(right) < 0) {

                // Case 3: "LEFT" points to positive element and "RIGHT" points to negative element.
                int temp = nums.get(left);
                nums.set(left, nums.get(right));
                nums.set(right, temp);

                ++left;
                --right;
            } 
            else {

                // Case 4: "LEFT" points to negative element and "RIGHT" points to positive element.
                ++left;
                --right;
            }

        }

        return nums;
    }
}

Python (3.5)

'''
    Time complexity: O(N)
	Space Complexity: O(1)

	Where N is the number of elements in the array.
'''

def separateNegativeAndPositive(nums):

    # Create two pointers- "LEFT" and "RIGHT".
    left = 0
    right = len(nums)-1

    while (left < right):

        if (nums[left] < 0 and nums[right] < 0):
            # Case 1: Both the pointers point to negative elements.
            left += 1

        elif (nums[left] >= 0 and nums[right] >= 0):
            # Case 2: Both the pointers point to positive elements.
            right -= 1

        elif (nums[left] >= 0 and nums[right] < 0):
            # Case 3: "LEFT" points to positive element and "RIGHT" points to negative element.
            get = nums[left], nums[right]
            nums[right], nums[left] = get
            left += 1
            right -= 1

        else:
            # Case 4: "LEFT" points to negative element and "RIGHT" points to positive element.
            left += 1
            right -= 1

    return nums

C++ (g++ 5.4)

/*

	Time complexity: O(N)

	Space Complexity: O(1)

	

	Where N is the number of elements in the array.

*/



vector < int > separateNegativeAndPositive(vector < int > & nums) {



    // Create two pointers- "LEFT" and "RIGHT".

    int left = 0;

    int right = nums.size() - 1;



    while (left < right) {



        if (nums[left] < 0 && nums[right] < 0) {



            // Case 1: Both the pointers point to negative elements.

            ++left;

        } 

        else if (nums[left] >= 0 && nums[right] >= 0) {

            

            // Case 2: Both the pointers point to positive elements.

            --right;

        } 

        else if (nums[left] >= 0 && nums[right] < 0) {



            // Case 3: "LEFT" points to positive element and "RIGHT" points to negative element.

            swap(nums[left], nums[right]);

            ++left;

            --right;

        } 

        else {



            // Case 4: "LEFT" points to negative element and "RIGHT" points to positive element.

            ++left;

            --right;

        }



    }



    return nums;

}

Accepted Answer

0

You are given an array 'ARR' consisting of 'N' integers. You need to rearrange the array elements such that all negative numbers appear before all positive numbers.

Follow Up:

Note:

Example:

Input format:

Output format:

Note:

Constraints:

Top Myntra Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Myntra Software Developer