Last Updated: 28 Jan, 2021
Move All Negative Numbers To Beginning And Positive To End
Easy
Asked in companies
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.
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.
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
Approaches
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.
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.
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.
Similar problems