/*
A sparse array stores only non‑zero values.
PHP's associative array 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 array of size maxIndex + 1
3. Fill with zeros
4. Copy sparse values into their positions
*/
function buildDense(array $sa): array
{
// Find largest index
$maxIndex = 0;
foreach ($sa as $index => $value) {
if ($index > $maxIndex) {
$maxIndex = $index;
}
}
// Allocate dense array filled with zeros
$dense = array_fill(0, $maxIndex + 1, 0);
// Copy sparse values
foreach ($sa as $index => $value) {
$dense[$index] = $value;
}
return $dense;
}
// Sparse entries (zero values omitted)
$sa = [
2 => 10,
10 => 7,
8 => 42,
3 => 5
];
$dense = buildDense($sa);
// Print dense array
echo "Dense array:\n[ ";
foreach ($dense as $v) {
echo $v . " ";
}
echo "]\n";
/*
run:
Dense array:
[ 0 0 10 5 0 0 0 0 42 0 7 ]
*/
