sparse to dense array javascript

Question

I have a sparse array in Javascript

const sparseArray = [
{"id":3, "value":"banana"},
{"id":7, "value":"coconut"}
];
const denseArraySize=10;

I would like to get :
const denseArray = [
{"id":0, "value":undefined},
{"id":1, "value":undefined}
{"id":2, "value":undefined},
{"id":3, "value":"banana"},
{"id":4, "value":undefined}
{"id":5, "value":undefined},
{"id":6, "value":undefined}
{"id":7, "value":"coconut"},
{"id":8, "value":undefined},
{"id":9, "value":undefined}
];

How do I get denseArray from sparseArray in a functional way.

Notice that sparceArray is sorted by id.

In C++, I was able to do this in linear time, lazily, using ranges::set_union().

In SQL, I would use a LEFT JOIN and COALESCE.

In Javascript, how can it be done ?

Answer 1

You've said you want to avoid a loop. I assume you mean a loop you write, since there will always be a loop involved, whether in your code or in a function you call.

The tool in the standard API that comes closest, I think, is Array.from with its mapping callback (probably starting out by mapping your current array into a Map by id for sublinear access times on id):

const sparseMap = new Map(sparseArray.map((element) => [element.id, element]));
const denseArray = Array.from({length: denseArraySize}, (_, id) => {
    const element = sparseMap.get(id);
    return element ?? {id, value: undefined};
});

Live Example:

const sparseArray = [
    {"id":3, "value":"banana"},
    {"id":7, "value":"coconut"}
];
const denseArraySize=10;

const sparseMap = new Map(sparseArray.map((element) => [element.id, element]));
const denseArray = Array.from({length: denseArraySize}, (_, id) => {
    const element = sparseMap.get(id);
    return element ?? {id, value: undefined};
});

console.log(denseArray);

.as-console-wrapper {
    max-height: 100% !important;
}

That's still a loop, though (two — we also have a loop building the Map). :-)

These two lines:

const element = sparseMap.get(id);
return element ?? {id, value: undefined};

can be written as one if you like:

return sparseMap.get(id) ?? {id, value: undefined};

I prefer to keep them separate so it's easy when I'm debugging to see where the element came from.

---

I probably wouldn't do it that way, I'd probably just write a simple loop:

const sparseMap = new Map(sparseArray.map((element) => [element.id, element]));
const denseArray = new Array(denseArraySize);
for (let id = 0; id < denseArray.length; ++id) {
    const element = sparseMap.get(id);
    denseArray[id] = element ?? {id, value: undefined};
}

Live Example:

const sparseArray = [
    {"id":3, "value":"banana"},
    {"id":7, "value":"coconut"}
];
const denseArraySize=10;

const sparseMap = new Map(sparseArray.map((element) => [element.id, element]));
const denseArray = new Array(denseArraySize);
for (let id = 0; id < denseArray.length; ++id) {
    const element = sparseMap.get(id);
    denseArray[id] = element ?? {id, value: undefined};
}

console.log(denseArray);

.as-console-wrapper {
    max-height: 100% !important;
}

And again, these two lines:

const element = sparseMap.get(id);
denseArray[id] = element ?? {id, value: undefined};

can be combined if you like:

denseArray[id] = sparseMap.get(id) ?? {id, value: undefined};