In-place array compaction with least amount of shifting

Question

I've been searching for an algorithm that can do array compaction with the least amount of movement of items. I know I can't go below O(N) and that's fine, but I'm not sure if even that's doable.

I'll use Lua for my examples. I assume -1 as my empty value as using nil will break the array part of the table in Lua (the array iteration only goes until it's first nil).

This is the desired outcome:

local arr = {1,3,4,-1,6,-1,8,-1,-1}
compact(arr)
-- arr: {1,3,4,8,6}

As you can see we only moved one item, 8 from it's old index 7 (lua uses 1-based indices) to it's new index 4.

I tried a few stuff, like iterating the array backwards, setting every -1 to nil (which is deleting that element) and keeping a hash map of free spots in the array that I can fetch so I can still do O(N). Unfortunately that didn't quite work.

Answer 1

You can do this in O(n) by using two indexes: one that moves from the beginning of the list, forward, and the other moving from the end of the list backward. Then, move forward in the list looking for the first empty spot. When you find one, move the index at the end of the list backwards to the first non-empty spot. Swap the two values. Repeat until the two indexes meet.

I should note that this does not maintain the relative order of items in the array. The OP's example suggests that maintaining order is not important.

Here's some pseudocode:

x = 0 // beginning of list
y = n-1 // last item in list
while (x < y)
{
    if (a[x] == -1)
    {
        // move y backwards, looking for the first non-empty element.
        while (y > x && a[y] == -1)
        {
            y = y - 1;
        }
        swap(a[x],a[y])
    }
    x = x + 1;
}