Shifting n times algorithm

Question

Given an array, starting from the beginning of the array till its end, whenever you encounter the number ‘2’, add another ‘2’ just after it.
In doing so, the last element in the array would be removed, because the final array should be the same size as the initial one.

For example, if the initial array is

[23, 2, 3, 12, 2, 2, 34, 55, 66, 79]

then the modified array should be

[23, 2, 2, 3, 12, 2, 2, 2, 2, 34]

Expected time complexity is O(n) and you should do it in place (using only constant amount of extra memory).

It's easy in O(n^2), but in O(n) ???

Answer 1

Make two passes through the array

1. Iterate through counting how many 2s you find, and keep track of how big the final array will be so you know when to stop. In your example, when you get to the 34 you should know that the last three elements don't matter because you've already seen three 2s before then. Remember where you stopped.
2. Go backwards through the array from where you stopped in the first pass. Copy each element to the end of the array. If it was a 2, copy it twice.

There is a corner case to handle where the last element that fits is a 2 but there is no room for its copy. You must account for this in both passes.