"""
A sparse list stores only non‑zero values.
Python's dict is a natural fit:
- Keys represent indices that actually exist
- Values represent stored data
- Lookup and insertion are fast
"""
from typing import Dict, List
def build_dense(sl: Dict[int, int]) -> List[int]:
"""
Converts sparse → dense.
Steps:
1. Find the maximum index in the sparse structure
2. Allocate a dense list of size max_index + 1
3. Fill with zeros (Python does this automatically)
4. Copy sparse values into their positions
"""
# Find largest index
max_index = max(sl.keys(), default=0)
# Allocate dense list
dense = [0] * (max_index + 1)
# Copy sparse values
for index, value in sl.items():
dense[index] = value
return dense
def main():
# Sparse entries (zero values omitted)
sl = {
2: 10,
10: 7,
8: 42,
3: 5
}
dense = build_dense(sl)
print("Dense list:")
print("[", *dense, "]")
if __name__ == "__main__":
main()
"""
run:
Dense list:
[ 0 0 10 5 0 0 0 0 42 0 7 ]
"""
