Shift Zeroes To Right

Problem Definition - Shift Zeroes To Right

We are trying to solve a problem at hand in which we are given an array of zeroes and positive integers. We need to Shift Zeroes To Right and positive integers to the left without disturbing the relative order of the positive integers.

Approach

I try to solve the problem in a simple way, you may find a similar problem on the web, here is a approach which solves this problem in O(N) time using constant auxiliary space (may be one or two extra variables). The first thing which comes in mind can be traversing the array and swapping zeroes with the positive integers. But wait! is this really the right direction?
Here is a simpler approach.
  • Start from the beginning of the array and maintain a counter nzC of number of non-zero elements.
  • Every time we find a non-zero element, put it in the array at index nzC, and increment the counter nzC by 1.
  • Once we break out of the loop, we fill the rest of the array with zero.
Source Code
public static void main(String[] args) {
    // declare the array
    int a[] = { 1, 0, 2, 0, 3, 0, 0, 0, 4, 5, 6, 7, 0, 0, 9 };

    int nzC= 0; // counter to maintain the number of non zero elements.
    for (int i = 0; i < a.length; i++) {
        // if we find a non zero assign it to the appropriate index and increment the counter.
        if (a[i] != 0) {
            a[nzC++] = a[i];
        }
    }

    // fill the remaining array with zeroes.
    for(;nzC< a.length;nzC++){
        a[nzC] = 0;
    }

    // print the array		
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i] + " , ");
    }
}

Analysis

Running Time : We traverse the array once in the first loop and in the second loop we will traverse the array at most once. Hence the running time would be O(N). Auxiliary Space As we can see there is not much of extra space required, we only used one extra variable for maintaining the counter. Don't forget to subscribe to TechieMe to get updates on latest posts.