import Foundation
/*
A sparse array stores only non‑zero values.
Swift's Dictionary<Int, Int> is a natural fit:
- Keys represent indices that actually exist
- Values represent stored data
- Lookup and insertion are fast
*/
typealias SparseArray = [Int: Int]
typealias DenseArray = [Int]
/*
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
*/
func buildDense(_ sa: SparseArray) -> DenseArray {
// Find largest index
let maxIndex: Int = sa.keys.max() ?? 0
// Allocate dense array filled with zeros
var dense: DenseArray = Array(repeating: 0, count: maxIndex + 1)
// Copy sparse values
for (index, value) in sa {
dense[index] = value
}
return dense
}
func main() {
// Sparse entries (zero values omitted)
let sa: SparseArray = [
2: 10,
10: 7,
8: 42,
3: 5
]
let dense: DenseArray = buildDense(sa)
print("Dense array:")
print("[ ", terminator: "")
dense.forEach { value in print("\(value) ", terminator: "") }
print("]")
}
main()
/*
run:
Dense array:
[ 0 0 10 5 0 0 0 0 42 0 7 ]
*/
