In this article, we’ll discuss in-depth, how to . We’ll also discuss 2 approaches to solve the below problem. move all negative elements to end Problem Statement An array contains both positive and negative numbers in random order. Rearrange the array elements so that all negative numbers appear before all positive numbers. Example: Input: N = 8 arr[] = {1, -1, 3, 2, -7, -5, 11, 6} Output: 1 3 2 11 6 -1 -7 -5 Input: N = 8 arr[] = {-5, 7, -3, -4, 9, 10, -1, 11} Output : 7 9 10 11 -5 -3 -4 -1 Solution We have an array of integers containing both positive and negative integers. We need to segregate the negative integers and put them at the end of the array. We will discuss two approaches to solve this problem. Approach 1 (Naive solution) A very basic approach that comes to mind to solve this problem is to use a copy array. First, traverse the array and store all the positive integers in the copy array. In the second iteration put all the negative integers in the end of the array. And now, copy the contents of the copy array to the original array. This way, we can get the negative integers seggreagated from the non-negative integers. #include <bits/stdc++.h> using namespace std; /* function to seggregate negative elements from the given array and moving them to the end */ void segregate_elements(int n,vector<int> &arr){ vector<int> temp; //copy array /* in the starting only copy the non-negative elements */ for(int i=0;i<n;i++){ if(arr[i]>=0) temp.push_back(arr[i]); } /* copy the negative elements to the end of dummy array */ for(int i=0;i<n;i++){ if(arr[i]<0) temp.push_back(arr[i]); } // copy the dummy array to the original array for(int i=0;i<n;i++){ arr[i]=temp[i]; } return; } int main() { //input int n; cin>>n; vector<int> arr(n); for(int i=0;i<n;i++){ cin>>arr[i]; } //segregating the array segregate_elements(n,arr); //output for(int i=0;i<n;i++){ cout<<arr[i]<<" "; } return 0; } Input 8 1 -1 3 2 -7 -5 11 6 Output 1 3 2 11 6 -1 -7 -5 Time complexity: O(n) Space complexity: O(n) Approach 2 (Two-pointer solution) In the naive solution we were using O(n) extra space so to make it more efficient we are going to solve it in O(1) space. In this approach we maintain two pointers, low and high. The low pointer is used for iteration purpose and high pointer is used to store the position after which all the elements are negative. The implementation of this approach is given below. #include <bits/stdc++.h> using namespace std; /* function to seggregate negative elements from the given array and moving them to the end */ void segregate_elements(int n,vector<int> &arr){ int low=0,high=n-1; /* making high point to the last non-negative integer in the array */ while(arr[high]<0 && high>low){ high--; } /* swap the low integer with high whenever we find a negative integer */ while(low<high){ if(arr[low]<0){ swap(arr[low],arr[high]); high--; } low++; } return; } int main() { //input int n; cin>>n; vector<int> arr(n); for(int i=0;i<n;i++){ cin>>arr[i]; } //segregating the array segregate_elements(n,arr); //output for(int i=0;i<n;i++){ cout<<arr[i]<<" "; } return 0; } Input 8 1 -1 3 2 -7 -5 11 6 Output 1 3 2 11 6 -1 -7 -5 Time complexity: O(n) Space complexity: O(1)
