Introduce a Data Structure or Abstract Data Type

This is where a study of data structures (and experience implementing and using them) really helps. If you can identify the bottleneck, you can start to try to throw data structures at the problem to see if there are any performance or spatial gains.

Going back to the Zeros to the End problem we did earlier, our bottleneck is likely the step of putting elements at different indexes. In that case, we may realize that using a counter variable is beneficial.

Note that the data structure doesn't need to be fancy. In our case, we're literally introducing a single int variable-- but sometimes that's all you need.

What should the counter be counting? Well, once we've split the array up into non-zeros ([1, 2, 3]) and zeros ([0, 0, 0]), we only really care about where the non-zeros end.

Because we don't need to worry about what is in the array after non-zero elements, we can simply keep a separate pointer to track the index of the final array. It will let us know where to start the zeros.

We could then write the follow pseudocode to utilize this strategy:

xxxxxxxxxx

insert_position = 0

for i in nums

  if i is not 0

    increase insert_position

    keep it in insert_position

  fill the rest in with 0