/*
A sparse array stores only non‑zero values.
TypeScript's Map<number, number> is a natural fit:
- Keys represent indices that actually exist
- Values represent stored data
- Lookup and insertion are fast
*/
type SparseArray = Map<number, number>;
type DenseArray = number[];
/*
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(sa: SparseArray): DenseArray {
let maxIndex: number = 0;
// Find largest index
for (const [index] of sa) {
if (index > maxIndex) {
maxIndex = index;
}
}
// Allocate dense list filled with zeros
const dense: DenseArray = Array(maxIndex + 1).fill(0);
// Copy sparse values
for (const [index, value] of sa) {
dense[index] = value;
}
return dense;
}
function main(): void {
// Sparse entries (zero values omitted)
const sa: SparseArray = new Map<number, number>([
[2, 10],
[10, 7],
[8, 42],
[3, 5]
]);
const dense: DenseArray = buildDense(sa);
console.log("Dense array:");
console.log("[", ...dense, "]");
}
main();
/*
run:
Dense array:
[ 0 0 10 5 0 0 0 0 42 0 7 ]
*/
