Rearranging an array without a second one

You get a big array (a numbered list of boxes) and you have to rearrange it. You might reverse it, push all the zeros to the end, or take some items out. The easy way is to make a new array and fill it. That works, but it uses twice the memory: for a while the old array and the new one both sit in memory.

Sometimes that is fine. Sometimes the array is huge, or the program reuses it thousands of times a second, and there is no memory for a second copy. Then you change the array you already have and use only a couple of extra variables. That is an in-place change: you edit the same array and never make a new one.

Take the first test, [0, 1, 0, 3]. The answer has to be [1, 3, 0, 0], and you may not build a second array to get there.

So you work inside the same four boxes. One marker, write, remembers which box gets the next number you keep. It starts at box 0. A second marker, read, looks at the boxes one by one from the left. When read finds a number that is not 0, you copy it into box write and move write one box to the right. The 1 lands in box 0, the 3 lands in box 1. Boxes 2 and 3 are then set to 0. The same four boxes now hold [1, 3, 0, 0], and no extra memory was needed. Saving that memory is the reason for the whole lesson.

"In place" means you edit the original boxes directly and spend almost no extra memory. Two moves solve most of these problems. Both use a pointer: a variable that holds a box number.

Two pointers from the ends (to reverse an array or swap items). Pointer lo starts at the first box, pointer hi at the last. Swap the two boxes they point at. Then move each one a step toward the other. Stop when they meet.

A write pointer (to move or remove items). A slow pointer write remembers where the next kept item goes. A fast pointer read walks the whole array. Each time read finds an item to keep, copy it into box write and move write one step forward.

Trace "zeros to the end" on [0, 1, 0, 3]. Read 0: skip it. Read 1: keep it, write it into box 0. The array is now [1, 1, 0, 3] and write is 1. Read 0: skip it. Read 3: keep it, write it into box 1. The array is now [1, 3, 0, 3] and write is 2. The kept numbers already stand at the front. Boxes 2 and 3 still hold old values, so fill them with zeros: [1, 3, 0, 0]. Done, with no second array.

Time is O(n): one walk over the array. Space is O(1): a couple of variables for the indices and one spare box for a swap. None of these grow with the array. A new array would cost O(n) extra memory, and here you may not spend it.

One catch in JavaScript: you cannot change a string in place. So these problems give you an array of characters instead (one letter per box). You edit the array, and the string stays as it was.

Before a program saves its log (the file where it writes down events), it removes private data from it. It does that without copying a big buffer (a stretch of memory that holds data). An input buffer gets cleaned up in place. A message gets packed into a network buffer of fixed size. A ring buffer gets maintained: a buffer of fixed size that fills up in a circle. In all of these, memory is tight or the same buffer is reused for every request. A fresh copy is wasted work there, and the write pointer lets you skip it.