How do you reorganize an array within O(n) runtime & O(1) space complexity?

Question

I'm a 'space-complexity' neophyte and was given a problem.

Suppose I have an array of arbitrary integers:
[1,0,4,2,1,0,5]

How would I reorder this array to have all the zeros at one end:
[1,4,2,1,5,0,0]

...and compute the count of non-zero integers (in this case: 5)?

... in O(n) runtime with O(1) space complexity?

I'm not good at this.
My background is more environmental engineering than computer science so I normally think in the abstract.

I thought I could do a sort, then count the non-zero integers.
Then I thought I could merely do a element-per-element copy as I re-arrange the array.
Then I thought something like a bubble sort, switching neighboring elements till I reached the end with the zeroes.
I thought I could save on the 'space-complexity' via shift array-members' addresses, being that the array point points to the array, with offsets to its members.

I either enhance the runtime at the expense of the space complexity or vice versa.

What's the solution?

Answer 1

Two-pointer approach will solve this task and keep within the time and memory constraints.

Start by placing one pointer at the end, another at the start of the array. Then decrement the end pointer until you see the first non-zero element.

Now the main loop:

• If the start pointer points to zero, swap it with the value pointed by the end pointer; then decrement the end pointer.
• Always increment the start pointer.
• Finish when start pointer becomes greater than or equal to the end pointer.

Finally, return the position of the start pointer - that's the number of nonzero elements.