def separateNegativeAndPositive(nums):
return sorted(nums)
Problem
Submissions
Hints & solutions
Discuss
Move All Negative Numbers To Beginning And Positive To End
Easy
0/40
Average time to solve is 10m
Contributed by
178 upvotes
Asked in companies
Problem statement
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.
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].
Detailed explanation ( Input/output format, Notes, Images )
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.
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
Sample Input 1:
2
5
1 -4 -2 5 3
2
2 1
Sample Output 1:
Yes
Yes
Explanation for Sample Input 1:
For the first test case we have, array: [1, -4, -2, 5, 3] and N = 5. On rearranging the array such that all negative numbers appear before all positive numbers we get the resulting array [-2, -4, 1, 5, 3].
For the second test case we have, array: [2, 1] and N = 2. There are no negative numbers. Hence, we do not require any rearrangement.
Sample Input 2:
3
4
1 -5 -5 3
5
-1 -2 3 4 5
1
-2
Sample Output 2:
Yes
Yes
Yes
Explanation for Sample Input 2:
For the first test case we have, array: [1, -5, -5, 3] and N = 4. On rearranging the array such that all negative numbers appear before all positive numbers we get the resulting array [-5, -5, 1, 3].
For the second test case we have, array: [-1, -2, 3, 4, 5] and N = 5. There are already arranged in required way. Hence, we do not require any rearrangement.
For the third test case we have, array: [-2 ] and N = 1. The array is already arranged in required way. Hence, we do not require any rearrangement.
Hint
Hint 1
Hint 2
Hint 3
Can you solve this problem by sorting the given array?
Approaches (3)
Approach 1
Approach 2
Approach 3
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.
Time Complexity
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).
Space Complexity
O(1)
Because no extra space is required.
Code Solution
(100% EXP penalty)
Move All Negative Numbers To Beginning And Positive To End
All tags
Sort by
Interview problems
java sol
public static int[] separateNegativeAndPositive(int a[]) {
ArrayList<Integer> neg = new ArrayList<>();
ArrayList<Integer> pos = new ArrayList<>();
for(int i =0;i<a.length;i++){
if(a[i] < 0) neg.add(a[i]);
else pos.add(a[i]);
}
int[] result = new int[a.length];
int index = 0;
for (int num : neg) result[index++] = num;
for (int num : pos) result[index++] = num;
return result;
}
13 views
0 replies
0 upvotes
Interview problems
C++ 3 Methods || STL, brute force , two pointers ||
#include <bits/stdc++.h>
vector<int> separateNegativeAndPositive(vector<int> &nums){
//method 1 using STL
/*
sort(nums.begin(), nums.end());
return nums;
*/
/* //method 2
//T.C=O(n^2)
int n = nums.size();
int s = 0;
vector<int>ans;
for(int i=0; i<n; i++){
if(nums[i] < 0){
ans.push_back(nums[i]);
}
}
for(int i=0; i<n; i++){
if(nums[i] >= 0){
ans.push_back(nums[i]);
}
}
return ans;
*/
//optimal solution O(n)
int n = nums.size();
int left =0;
int right = n-1;
while(left <= right){
if(nums[left] < 0 && nums[right] >=0){
left++;
right--;
}
else if(nums[left] >= 0 && nums[right] < 0){
swap(nums[left++],nums[right--]);
}
else if(nums[left] >= 0){
right--;
}
else{
left++;
}
}
return nums;
}
62 views
0 replies
0 upvotes
Interview problems
o(n) solution || cpp || 3 Pointer
//similar approach to Dutch National Flag Problem
#include <bits/stdc++.h>
vector<int> separateNegativeAndPositive(vector<int> &nums){
// Write your code here.
int low =0;
int high = nums.size()-1;
int curr = 0;
while(curr<=high){
if(nums[curr] <0){
swap(nums[curr],nums[low]);
low++;
curr++;
}
else{
swap(nums[curr],nums[high]);
high--;
}
}
return nums;
};
81 views
0 replies
0 upvotes
Interview problems
i don't know why it's not passing one test case ,some one help
vector<int> separateNegativeAndPositive(vector<int> &nums){
int n = nums.size();
int i = 0, j = n-1;
while(i<j){
if(nums[i]<0 && nums[j]<0){
i++;
}
else if(nums[i]>0 && nums[j]<0){
swap(nums[i], nums[j]);
i++;
j--;
}
else if(nums[i]>0 && nums[j]>0){
j--;
}
else{
i++;
j--;
}
}
return nums;
}
74 views
1 reply
0 upvotes
Interview problems
Java test case fail!!
I don't know why this test case shown fail while submission! 5
5 1 -4 -2 5 3 2 2 1 4 1 -5 -5 3 5 -1 -2 3 4 5 1 -2 But successfully running when I'm running this code. https://ibb.co/jZ3bwDJ
35 views
1 reply
0 upvotes
Interview problems
Easiest of all Solution
#include <bits/stdc++.h>
vector<int> separateNegativeAndPositive(vector<int> &nums){
sort(nums.begin(),nums.end() );
vector<int> a;
for ( int i =0 ; i < nums.size(); i++){
a.push_back(nums[i]);
}
return a;
}
141 views
0 replies
2 upvotes
Interview problems
Move All Negative Numbers To Beginning And Positive To End || Easy Understanding
#include <bits/stdc++.h>
vector<int> separateNegativeAndPositive(vector<int> &nums){
// Write your code here.
vector<int>ne,po,ans;
int m=nums.size();
for(int i=0;i<m;i++){
if(nums[i]<0){
ne.push_back(nums[i]);
}else{
po.push_back(nums[i]);
}
}
for(int i=0;i<ne.size();i++){
ans.push_back(ne[i]);
}
for(int i=0;i<po.size();i++){
ans.push_back(po[i]);
}
return ans;
}
75 views
0 replies
0 upvotes
Interview problems
Two Lines C++ code. Very Very Easy | STL SORT CODE
#include <bits/stdc++.h>
vector<int> separateNegativeAndPositive(vector<int> &nums){
sort(nums.begin(),nums.end());
return nums;
}
93 views
1 reply
0 upvotes
Interview problems
c++ one line solution && two pointer approach
solution 1;
vector<int> separateNegativeAndPositive(vector<int> &nums){
sort(nums.begin() , nums.end());
return nums;
}
solution 2;
vector<int> separateNegativeAndPositive(vector<int> &nums){
int s = 0;
int e = nums.size()-1;
while(s<e){
if(nums[s] < 0){
s++;
}
else if(nums[e] > 0){
e--;
}
else{
swap(nums[s] , nums[e]);
}
}
return nums;
}
102 views
0 replies
1 upvote
1
2
3
4
C++ (g++ 5.4)
Console