InterviewQ: ZeroesToTheRight Solution

This post is part of my Interview Guide series in which I log my journey to Software Engineering Wizardom.

Here’s the prompt as it appears in my January 2016 Interview Questions post:

---

Write a function that takes an integer array and moves all the zeroes in it to the right of the array. Implement this in-place. It doesn’t matter if the order of the other integers is changed, just that they are still present.

Example:

[1,0,7,0,0,6,0] -> [1,7,6,0,0,0,0]

---

You can find my solution on GitHub.

The way I implemented it was to run a version of insertion sort where the “sorted” partition is on the right side where the zeroes go.

Here, I keep track of two pointers. The first pointer (zeroPtr) keeps track of the index directly to the left of the sorted partition. This holds the position of the element I want to switch in the event I find another zero.

The second pointer (findPtr) goes through the rest of the array in order to find any remaining zeroes.

If it does find a zero, we place the integer at index zeroPtr at our findPtr index. We don’t have to worry about saving the value at findPtr, because we know we’re only performing this action if we’ve found a 0, in which case we can just place a 0 at zeroPtr. Of course, we must now update zeroPtr to reflect the new end of the sorted partition.

Otherwise, findPtr decrements and continues iterating through the array.

My implementation:

(https://gist.github.com/SIRHAMY/9bbb9218ad360c40ea04)