558 views
0 votes
0 votes
Consider an array of length n consisting only of positive and negative integers. Design an algorithm to rearrange the array so that all the negative integers appear before all the positive integers, using $O(n)$ time and only a constant amount of extra space.

1 Answer

0 votes
0 votes

rearrange(A):

int i = -1, len = A.length;
for(int j = 0; j < len; j++){
      if(A[j] <= 0){
           int tmp = A[i+1];
           A[i+1] = A[j];
           A[j] = tmp;
           ++i;
        }
 }

 

edited by

Related questions

1 votes
1 votes
3 answers
4