SparseArray is #3 from the from the 2015 AP Computer Science A Free Response problems.

Part (a) getValueAt method

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

    return 0;

Recognizing that the instance variable entries stores an ArrayList, rather than a 2D array, is critical.

Since the elements in entries are unordered this is just a sequential/linear search.

Part (b) removeColumn method

public void removeColumn(int col)
    for(int i = entries.size() - 1; i >= 0; i--)
        SparseArrayEntry entry = entries.get(i);

        if(entry.getCol() == col)
        else if(entry.getCol() > col)
            entries.set(i, new SparseArrayEntry(
                    entry.getRow(), entry.getCol() - 1, entry.getValue()));


Removing a column can be accomplished with a single traversal of entries. SparseArrayEntry objects are immutable so new objects must be created for the entries with column values greater than col.

See ArrayList practice for details on adding to and removing from an ArrayList within a loop.

2015 AP CS Exam Free Response Solutions

Additional resources for ArrayList objects


Comment on SparseArray