#
# A sparse array stores only non‑zero values.
# Ruby's Hash is a natural fit:
# - Keys represent indices that actually exist
# - Values represent stored data
# - Lookup and insertion are fast
#
# Sparse array type (conceptual)
SparseArray = Hash
DenseArray = Array
#
# build_dense:
# Converts sparse → dense.
#
# Steps:
# 1. Find the maximum index in the sparse structure
# 2. Allocate a dense array of size max_index + 1
# 3. Fill with zeros
# 4. Copy sparse values into their positions
#
# sa :: Hash{Integer => Integer}
# returns :: Array<Integer>
#
def build_dense(sa)
# Find largest index
max_index = sa.keys.max || 0
# Allocate dense array filled with zeros
dense = Array.new(max_index + 1, 0)
# Copy sparse values
sa.each do |index, value|
dense[index] = value
end
dense
end
def main
# Sparse entries (zero values omitted)
sa = {
2 => 10,
10 => 7,
8 => 42,
3 => 5
}
dense = build_dense(sa)
puts "Dense array:"
print "[ "
dense.each { |v| print "#{v} " }
puts "]"
end
main
# run:
#
# Dense array:
# [ 0 0 10 5 0 0 0 0 42 0 7 ]
#
