Question

How to build sparse array in Java

Answer 1

import java.util.ArrayList;
import java.util.List;

/**
    A small sparse array representation:
    - Each entry stores an index and a value
    - Zero values are simply not included
*/

class SparseEntry {
    int index;
    int value;

    SparseEntry(int index, int value) {
        this.index = index;
        this.value = value;
    }
}

/**
    buildDense:
    Converts sparse entries into a dense array.

    Steps:
    1. Find the largest index
    2. Allocate an array of size maxIndex + 1
    3. Fill with zeros (Java does this automatically)
    4. Copy sparse values into their positions
*/
public class SparseToDense {

    public static int[] buildDense(List<SparseEntry> sa) {
        int maxIndex = 0;

        // Find largest index
        for (SparseEntry e : sa) {
            if (e.index > maxIndex) {
                maxIndex = e.index;
            }
        }

        // Allocate dense array filled with zeros
        int[] dense = new int[maxIndex + 1];

        // Copy sparse values
        for (SparseEntry e : sa) {
            dense[e.index] = e.value;
        }

        return dense;
    }

    public static void main(String[] args) {
        // Sparse entries (zero values omitted)
        List<SparseEntry> sa = new ArrayList<>();
        sa.add(new SparseEntry(2, 10));
        sa.add(new SparseEntry(10, 7));
        sa.add(new SparseEntry(8, 42));
        sa.add(new SparseEntry(3, 5));

        int[] dense = buildDense(sa);

        System.out.print("Dense array:\n[ ");
        for (int v : dense) {
            System.out.print(v + " ");
        }
        System.out.println("]");
    }
}


/*
run:

Dense array:
[ 0 0 10 5 0 0 0 0 42 0 7 ]

*/

 

70+ SQL courses for beginners and professionals

Answer 2

import java.util.HashMap;
import java.util.Map;

/**
    A sparse array stores only non‑zero values.
    HashMap<Integer, Integer> is a natural fit:
      - Keys represent indices that actually exist
      - Values represent stored data
      - Lookup and insertion are fast
*/

public class SparseToDense {

    /**
        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 (Java does this automatically)
        4. Copy sparse values into their positions
    */
    public static int[] buildDense(Map<Integer, Integer> sa) {
        int maxIndex = 0;

        // Find largest index
        for (Map.Entry<Integer, Integer> entry : sa.entrySet()) {
            int index = entry.getKey();
            if (index > maxIndex) {
                maxIndex = index;
            }
        }

        // Allocate dense array
        int[] dense = new int[maxIndex + 1];

        // Copy sparse values
        for (Map.Entry<Integer, Integer> entry : sa.entrySet()) {
            dense[entry.getKey()] = entry.getValue();
        }

        return dense;
    }

    public static void main(String[] args) {

        // Sparse entries (zero values omitted)
        Map<Integer, Integer> sa = new HashMap<>();
        sa.put(2, 10);
        sa.put(10, 7);
        sa.put(8, 42);
        sa.put(3, 5);

        int[] dense = buildDense(sa);

        System.out.println("Dense array:");
        System.out.print("[ ");
        for (int v : dense) {
            System.out.print(v + " ");
        }
        System.out.println("]");
    }
}


/*
run:

Dense array:
[ 0 0 10 5 0 0 0 0 42 0 7 ]

*/

 

70+ SQL courses for beginners and professionals