#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
/*
The sparse array stores only non‑zero values.
We scan it to find the maximum index.
We allocate a dense vector of size maxIndex + 1, filled with zeros.
We copy each sparse entry into its position.
*/
// Sparse array type
using SparseArray = std::unordered_map<size_t, int>;
// Convert sparse → dense
std::vector<int> buildDense(const SparseArray& sa) {
// Find the largest index so we know how big the dense array must be
size_t maxIndex = 0;
for (const auto& [index, value] : sa) {
maxIndex = std::max(maxIndex, index);
}
// Allocate dense array filled with zeros
std::vector<int> dense(maxIndex + 1, 0);
// Copy sparse values into dense array
for (const auto& [index, value] : sa) {
dense[index] = value;
}
return dense;
}
int main() {
// Sparse entries (zero values omitted)
SparseArray sa = {
{2, 10},
{10, 7},
{8, 42},
{3, 5}
};
auto dense = buildDense(sa);
std::cout << "Dense array:\n[ ";
for (int v : dense) {
std::cout << v << " ";
}
std::cout << "]\n";
}
/*
run:
Dense array:
[ 0 0 10 5 0 0 0 0 42 0 7 ]
*/
