How to store which index ranges are free in an array?

Say you have a large array which stores arbitrary objects. Every now and then an object is removed here and removed there. Now you want to keep track of the empty slots in the array so they can be filled up and don’t go to waste. What is the best way to keep track of the empty space in a compact yet efficient way?

By compact I mean, instead of storing every removed index in another array, it should store the removed index and the size of slots available after that index. How can it do that efficiently without using a hash table?

So for example:

// step 1
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p] // added

// step 2..n eventually lands us to:
[a, -, -, d, e, f, -, -, -, -, -, l, -, n, -, p] // added
[-, b, c, -, -, -, g, h, i, j, k, -, m, -, o, -] // removed

// then compacted, the removed array would look more like:
[1:2,6:5,12:1,14:1] // removed

What would an algorithm look like to implement this?

let array1 = [] // added/items array
let array2 = [] // removed/free array

function removeFromArray1Naive1(index) {
  array1[index] = null
  array2[index] = true
}

function removeFromArray1Naive2(index) {
  array1[index] = null
  array2.push(index)
}

function removeFromArray1MaybeBetter(index) {
  array1[index] = null
  // ?
}

In the end, after adding and removing a bunch of items and the added array is empty, we would end up with this removed array:

[{ index: 0, count: 16 }] // or however many there were.

With a hash table I don’t even think you could do it well. Any ideas how to do this well (i.e. to fit the constraints)?

A linked list would be compact, but to know where to insert/increment a newly removed index, you would have to traverse the array. A B+tree might solve this by balancing the operations with compaction, but it might require a lot of rewriting. Not sure if anything is better. Basically I want buckets to fill up appropriately.

Hmm… I guess we don’t care about the order of the indexes removed, so maybe that helps.

If there’s any clever technique that slightly reframes the problem and does something interesting to solve the overall objective, that would work too. For example, if you had buckets and just threw items in a coarse bucket, then compactified later, sort of thing.

48 thoughts on “How to store which index ranges are free in an array?”

  1. With the one change that where I am using findIndex you should use a binary search, the below seems to work pretty well (where the first item in each array is the index in the original array, and the second item is the length of empty items):

    let arr = Array.from(Array(1000).keys())
    let removed = [];
    let remove = (index) => {
        arr[index] = null;
        // find the index of the first removed element > index
        const i = removed.findIndex(([i]) => i > index);
        if (i === -1) {
            // there is no element greater, first check last element
            if (removed.length && removed[removed.length - 1][0] === index - 1) {
                removed[removed.length - 1][1]++;
                return
            }
            removed.push([index, 1]);
            return;
        }
        let [pos, length] = removed[i];
        // if the next element greater than index is index + 1,
        // decrement it and increase the length
        if (pos === index + 1) {
            removed[i][0]--;
            removed[i][1]++;
            // if the previous element is equal to index - 1, merge them
            if (i > 0 && removed[i-1][0] === index - 1) {
                removed[i][0] -= removed[i-1][0];
                removed[i][1] += removed[i-1][1];
                removed.splice(i-1, 1);
            }
            return;
        }
        // if it's the first element, there is no previous, so we should just add it
        if (i === 0) {
            removed.unshift([index, 1]);
            return
        }
        [pos, length] = removed[i-1];
        // pos and length are now the first element removed before this index
        if (pos === index - 1) {
            removed[i-1][1]++;
        }
    }
    
    remove(5);
    console.log(removed);
    remove(10);
    console.log(removed);
    remove(11);
    console.log(removed);
    remove(9);
    remove(1);
    console.log(removed)
    Reply

Leave a Comment