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

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.

  • Jani Kettunen

    Unfortunately this solution fails for the following input: [4 4 9 2 4 9 2 4] and [8 2 3 3 8 3 3 8]

    • Hi Jani,

      I tested the source code against the input. It works fine, also this input doesn't contain any zero so the output array is same as the input array. Hope this helps.

      • Jani Kettunen

        Whoops sorry, that comment was supposed to go to the Arrays are permutations of each other -post. I'll repost it there.