public class Main{
    public static void main (String args[]){
        SparseArray arr = new SparseArray();
        // System.out.println(arr.getValueAt(3, 1));
        arr.printEntries();
        arr.removeColumn(1);
        arr.printEntries();
        // System.out.println(arr.getValueAt(3, 1));
        // System.out.println(arr.getValueAt(1, 3));
    }
}

public class SparseArrayEntry{
    private int row;
    private int col;
    private int value;

    public SparseArrayEntry(int r, int c, int v){
        row = r;
        col = c;
        value = v;
    }
    public int getRow(){
        return row;
    }

    public int getCol(){
        return col;
    }

    public int getValue(){
        return value;
    }
}

public class SparseArray{
    private int numRows;
    private int numCols;
    private List<SparseArrayEntry> entries;

    public SparseArray(){
        entries = new ArrayList<SparseArrayEntry>();
        entries.add(new SparseArrayEntry(1, 4, 4));
        entries.add(new SparseArrayEntry(2, 0, 1));
        entries.add(new SparseArrayEntry(3, 1, -9));
        entries.add(new SparseArrayEntry(1, 1, 5));
    }

    public int getNumRows(){
        return numRows;
    }

    public int getNumCols(){
        return numCols;
    }

    public int getValueAt(int row, int col){
        for (SparseArrayEntry e : entries){
            if (e.getRow() == row && e.getCol() == col){
                return e.getValue();
            }
        }
        return 0;
    }

    public void printEntries(){
        for (SparseArrayEntry e : entries){
            System.out.println(String.valueOf(e.getRow()) + " " + String.valueOf(e.getCol()) + " " + String.valueOf(e.getValue()));
        }
    }

    public void removeColumn(int col){
        numCols --;
        ArrayList<SparseArrayEntry> removeList = new ArrayList<SparseArrayEntry>();
        int iterator = entries.size();
        for (int i = 0; i < iterator; i ++){
            if (entries.get(i).getCol() == col){
                removeList.add(entries.get(i));
            }
            else if (entries.get(i).getCol() > col){
                System.out.println("new col" + String.valueOf(entries.get(i).getCol() - 1));
                entries.add(new SparseArrayEntry(entries.get(i).getRow(), entries.get(i).getCol() - 1, entries.get(i).getValue()));
                removeList.add(entries.get(i));
            }
        }
        for (SparseArrayEntry e : removeList){
            entries.remove(e);
        }
    }
}
Main.main(null);

1 4 4
2 0 1
3 1 -9
1 1 5
new col3
2 0 1
1 3 4

Learnings:

  1. You can’t remove an entry in a list while iterating over it like using an enhanced for loop. Instead you can use an iterator.
  2. to get the length of an arraylist is use .size()
  3. using the size of a list to iterate until is dynamic, so it changes as the list gets bigger. Makes sense because the check is rerun every time.

Reflection:

The main theme of this FRQ was working with 2d arrays kind of. I had never actually heard of a sparse array before this FRQ, so it was interesting to learn about what it is and how it works. It makes sense to not use an actual array datatype to represent a sparse array because so many of the entries are the same. Theoretically this could be done with any array with primarily a single type of data. However, that wouldn’t make as much intuitive sense as a sparse array.