package main
import (
"fmt"
)
/*
A sparse array stores only non‑zero values.
Go's map[int]int is a natural fit:
- Keys represent indices that actually exist
- Values represent stored data
- Lookup and insertion are fast
*/
type SparseArray map[int]int
type DenseArray []int
/*
buildDense:
Converts sparse → dense.
Steps:
1. Find the maximum index in the sparse structure
2. Allocate a dense slice of size maxIndex + 1
3. Fill with zeros (Go does this automatically)
4. Copy sparse values into their positions
*/
func buildDense(sa SparseArray) DenseArray {
var maxIndex int = 0
// Find largest index
for index := range sa {
if index > maxIndex {
maxIndex = index
}
}
// Allocate dense slice filled with zeros
dense := make(DenseArray, maxIndex+1)
// Copy sparse values
for index, value := range sa {
dense[index] = value
}
return dense
}
func main() {
// Sparse entries (zero values omitted)
sa := SparseArray{
2: 10,
10: 7,
8: 42,
3: 5,
}
dense := buildDense(sa)
fmt.Println("Dense array:")
fmt.Print("[ ")
for _, v := range dense {
fmt.Print(v, " ")
}
fmt.Println("]")
}
/*
run:
Dense array:
[ 0 0 10 5 0 0 0 0 42 0 7 ]
*/
