/*
A sparse array stores only non‑zero values.
JavaScript's Map is a natural fit:
- Keys represent indices that actually exist
- Values represent stored data
- Lookup and insertion are fast
*/
/*
buildDense:
Converts sparse → dense.
Steps:
1. Find the maximum index in the sparse structure
2. Allocate a dense list of size maxIndex + 1
3. Fill with zeros
4. Copy sparse values into their positions
*/
function buildDense(sparse) {
let maxIndex = 0;
// Find largest index
for (const [index] of sparse) {
if (index > maxIndex) {
maxIndex = index;
}
}
// Allocate dense list filled with zeros
const dense = Array(maxIndex + 1).fill(0);
// Copy sparse values
for (const [index, value] of sparse) {
dense[index] = value;
}
return dense;
}
function main() {
// Sparse entries (zero values omitted)
const sparse = new Map([
[2, 10],
[10, 7],
[8, 42],
[3, 5]
]);
const dense = buildDense(sparse);
console.log("Dense array:");
console.log("[", ...dense, "]");
}
main();
/*
run:
Dense array:
[ 0 0 10 5 0 0 0 0 42 0 7 ]
*/
