Order the array to have zeros in front

This is a typical interview question asked in interviews “how would you move all zeros in an array to the front?”

Such a question is aimed to test the candidate’s grasp of basic algorithm and thought process.

Many a times, the details of the problem statement are not provided (some times intentionally).

So before you jump into giving the solution, it is imperative that you understand the requirement correctly and completely.

Example, for this question, valid counter question (sometimes expected by the interviewer) would be like:
1> Can you provide an example?
2> After reordering the array, would you like to maintain the order of other(non-zero) numbers?

The above questions by you would indicate
1> you believe that requirement gathering comes before implementation
2> you are thinking

DON’Ts:
Some questions should NOT be asked
1> Do you want the solution to be time efficient? (Well ofcourse!!)
2> Can I use another/temporary array to solve this? (It’s upto you!!!)

Also, Some developers often opt for a shortcut in implementation, providing bad solution.
In this case: Sorting

This is inappropriate because:
1> Incorrect solution: what if array contains negative numbers.
2> Not generic: what if the requirement is tweaked to move the 9s instead of 0s
3> Inefficient: a lot of operations will be done even for an array like, {0,0,5,4,3,2,1}, which was not necessary

Case 1> We just want the zeros in the front part and we don’t care about the other numbers

Idea is to provide a simple, generic, time efficient solution without using temporary array.


static int[] arr = new int[]{2,0,0,1,7,3,0,5,9,0,6,8,0,3};

void performWithoutOrder(int[] arr){
  int counter = 0;        
  int positionIndex = 0;  
  
  while (counter < arr.length) {
    if(arr[counter] == 0){
      swap(arr, counter, positionIndex);
      positionIndex++;
    }
    counter++;
  }
}

void swap(int[] arr, int indx1, int indx2){
   int t = arr[indx1];
   arr[indx1] = arr[indx2];
   arr[indx2] = t;
}

Case 2: We would you like to maintain the order of other(non-zero) numbers

Input Array: {2,0,0,1,7,3,0,5,9,0,6,8,0,3}
Output Array: {0,0,0,0,0,2,1,7,3,5,9,6,8,3}


void performMaintainingOrder(int[] arr){
  int counter = arr.length - 1;        
  int positionIndex = arr.length - 1;
        
  while (counter >= 0) {
    if(arr[counter] != 0){
      swap(arr, counter, positionIndex);
      positionIndex--;
    }
  counter--;
  }
}

Please note that even for case 2 (which is trickier), we have maintained the time complexity and the algorithm just makes 1 pass over the array, T(n) is O(n).

Advertisements

One response to “Order the array to have zeros in front

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s