Move Negative Elements to the end

Given an array of size n with negative and positive elements, the task is to place all negative elements to the end keeping all positive elements in the beginning(Full Question)

  • Take two pointers start and last initially pointing to 0 and n-1 respectively
  • We come across four scenarios while we iterate
  • one where the value at the start is less than zero and the value, at last, is greater than zero, in which case we swap the elements and increment, decrements the index start, last
  • two where the value at the start is less than zero and the value at the last also is less than zero when we just decrement the index at last as to keep the values unchanged
  • three where the value at the start is greater than zero and the values at the last is greater than zero too in which case we increment the start index
  • In the last case where both values at the start and last are as expected and need no swapping we increment and decrement the index at the start and last without any changes
  • this algorithm has O(n) time complexity with O(1) space complexity
public void segregateElements(int arr[], int n)
{
int start=0;
int last=n-1;
int temp=0;
while(start<last){
if(arr[start]<0 && arr[last]>=0){
temp=arr[start];
arr[start]=arr[last];
arr[last]=temp;
start++;
last--;
}
else if(arr[start]<0 && arr[last]<0){
last--;
}
else if(arr[start]>=0 && arr[last]>=0){
start++;
}
else{
start++;
last--;
}
}
}
  • This algorithm does not suffice the requirements in the question though
  • the output does not return elements in the same order as input hence we will have to introduce a temp array
  • This temp array keeps track of and preserves the order of the elements in the given array
public void segregateElements(int arr[], int n)
{
// Your code goes here
int[] temp=new int[n];
int j=0;
for(int i=0;i<n;i++){
if(arr[i]>=0)
temp[j++]=arr[i];
}
if(j==n || j==0)
return;
for(int i=0;i<n;i++){
if(arr[i]<0)
temp[j++]=arr[i];
}
for(int i=0;i<n;i++){
arr[i]=temp[i];
}
}
  • this algorithm takes O(n) time complexity with O(n) extra space

Intimidated developer trying to find her way into technology dominant world