Multiple pointers is key.
Because we don't need or care about what is in the array after non-zero elements, we can simply keep a separate pointer of where to start the zeros. This extra pointer will prevent us from having to store a separate temp
array, with the intuition being that we know what we need to fill after (exclusively 0
s!).
Despite having two loops, the time complexity simplifies to O(n)
. However, the space complexity is constant since we're using the same array.
Follow the below illustration for more guidance:
