Push the Empty Boxes to the Back

A store shelf is written down as a row of box weights, where a 0 means an empty box. The manager wants all the empty boxes pushed to the far end of the shelf, while the boxes that have something in them stay in the same order as before.

Return the shelf after the empties have been pushed back.

Examples

Example 1

Input:  shelf = [0, 5, 0, 3]
Output: [5, 3, 0, 0]

Walking the shelf 0, 5, 0, 3, the non-empty boxes are 5 and 3, written to the front in that order. The two empty boxes then fill the rest, giving [5, 3, 0, 0].

Example 2

Input:  shelf = [0]
Output: [0]

Example 3

Input:  shelf = [1, 2, 3]
Output: [1, 2, 3]

Constraints

shelf has 1 to 10,000 weights, each between 0 and 10,000.

The non-zero weights must keep their original order; all the zeros end up after them. Do it without sorting the shelf.

How to solve it

Hint

Keep a second index that says where the next non-empty box should be written.

Approach: Write pointer (stable partition)

Keep a write index starting at 0.
Walk the shelf; every time you meet a non-zero weight, write it at write and move write on by one.
Fill the rest of the shelf, from write to the end, with zeros.

Check with the example. [0, 5, 0, 3] writes 5 then 3 at the front, then fills the last two slots with zeros.

Complexity: O(n) time, O(1) extra space.

The reference solutions in all four languages are in the Solutions tab of the workspace below.