SparseArray: 2015 FRQ 3

Representing a mostly-empty grid without wasting memory on all those zeros is the idea behind this AP Computer Science A free-response question — you look up and remove entries from a list-backed sparse array instead of a full two-dimensional array.

What This FRQ Tests

• AP CSA units: Unit 7 (ArrayList)
• Core skill: searching an ArrayList of objects for a match based on more than one field at once
• Secondary skill: safely removing and updating elements of an ArrayList while iterating over it, without corrupting the indices still left to check
• Official category: this year's FRQ 3 tests Array/ArrayList content (Unit 7), matching what's now the modern FRQ-3 slot — though as with every pre-2019 exam, that alignment isn't guaranteed and is confirmed here by the question's actual content, not assumed from its number alone.

The Setup

• SparseArrayEntry (given, complete, and immutable — it "cannot be modified after it has been constructed") represents one non-zero value in the grid:
  • int getRow(), int getCol(), int getValue()
• SparseArray represents the whole grid:
  • private int numRows, private int numCols
  • private List<SparseArrayEntry> entries — only the non-zero elements are stored, in no particular order
• You're asked to write two methods:
  • getValueAt(int row, int col) — looks up the value at a given position, or 0 if nothing is stored there
  • removeColumn(int col) — deletes an entire column, shifting every entry to its right one column to the left

Part (a): Writing getValueAt(int row, int col)

Step-by-Step Approach

1. Loop through every entry currently in the list.
2. For each one, check whether its row and its column both match what was asked for.
3. If they match, return that entry's value immediately.
4. If the loop finishes without finding a match, the position must be an implicit zero — return 0.

The Code

public int getValueAt(int row, int col)
{
    for (int i = 0; i < entries.size(); i++)
    {
        SparseArrayEntry entry = entries.get(i);

        if (entry.getRow() == row && entry.getCol() == col)
        {
            return entry.getValue();
        }
    }

    return 0;
}

Why Each Piece Matters

• Both getRow() and getCol() have to match — checking only one would return the value from the wrong entry whenever two entries happen to share a row, or share a column.
• Returning inside the loop as soon as a match is found avoids needlessly checking the remaining entries.
• return 0 after the loop is what makes "no entry found" mean the same thing as "this position holds zero" — exactly how a sparse array is supposed to behave, since only non-zero values get stored at all.

Tracing the Example

Using the question's own sample sparse object, whose entries list holds (row, col, value) triples (1, 4, 4), (2, 0, 1), (3, 1, -9), (1, 1, 5):

• sparse.getValueAt(3, 1) — checks (1,4,4) (no match), (2,0,1) (no match), (3,1,-9) (row and column both match) → returns -9
• sparse.getValueAt(3, 3) — no entry in the list has both row 3 and column 3 (the only row-3 entry has column 1) → loop finishes → returns 0

Both results match the question exactly.

Common Mistakes to Avoid

• Checking only the row or only the column, not both together in the same condition.
• Returning 0 the moment a single non-matching entry is checked, instead of waiting until the entire list has been searched.
• Assuming an empty entries list is a special case that needs its own check — it isn't. The loop simply never executes, and 0 is returned by default, which is exactly correct for an all-zero array.

Part (b): Writing removeColumn(int col)

The Rule, Broken Down

1. Every entry whose column matches col is deleted entirely — that column no longer exists.
2. Every entry whose column is greater than col needs its column index reduced by one, since everything to the right of the removed column shifts left.
3. Entries whose column is less than col are left untouched.
4. numCols itself has to shrink by one, to reflect the missing column.

Step-by-Step Approach

1. Since SparseArrayEntry objects are immutable, an entry that needs a new column can't have its field reassigned — it has to be replaced with a brand-new SparseArrayEntry, put back into the same list position with set.
2. Walk through the list, checking each entry's column against col.
3. An exact match gets removed from the list entirely.
4. A column greater than col gets replaced with a new entry — same row, same value, column minus one.
5. Reduce numCols by one, exactly once, after the list has been fully processed.
6. The trickiest part: removing elements from an ArrayList while looping over it in the normal forward direction skips entries, because every remove call shifts everything after it one position to the left. Looping backward instead — from the last index down to 0 — sidesteps this entirely, since any entry already visited never moves, no matter what gets removed further down the list.

The Code

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

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

    numCols--;
}

Why Each Piece Matters

• Looping backward (i--, starting at entries.size() - 1) is the detail that makes the whole method correct. Removing index i only shifts elements at positions after i — and in a backward loop, those have already been checked. A forward loop would instead skip whichever entry slides into a just-removed position.
• Building a new SparseArrayEntry instead of modifying the existing one — the problem states directly that these objects "cannot be modified after it has been constructed," so there's no setter to call even if one seemed convenient.
• entries.set(i, shifted) replaces the old entry in place at the same index, rather than removing it and adding a new one at the end (which would scramble the list's order for no reason).
• numCols-- happens once, outside the loop — it's a property of the array as a whole, not something tied to any individual entry.

Tracing the Example

Walking backward through the question's sample list — entries (1, 4, 4) at index 0, (2, 0, 1) at index 1, (3, 1, -9) at index 2, (1, 1, 5) at index 3 — for the call sparse.removeColumn(1):

Final list: {(1, 3, 4), (2, 0, 1)}, and numCols drops from 5 to 4 — matching the question's expected result exactly (the question itself notes the order within the list doesn't matter).

Common Mistakes to Avoid

• Looping forward while removing. This is the single most common bug on exactly this style of ArrayList problem — it's specifically why this solution loops backward instead.
• Trying to call something like entry.setCol(...). There is no such method; SparseArrayEntry is immutable by design, so a new object is the only option.
• Mixing up > and ==. An entry exactly at the removed column gets deleted, not shifted — only entries strictly greater than col get their column reduced.
• Decrementing numCols inside the loop, which would subtract more than 1 total if the loop body ever ran more than once.

Key Takeaways

• When removing elements from an ArrayList while iterating over it by index, loop backward — it's the simplest way to guarantee removals never cause an element to get skipped.
• An immutable object can't be edited in place; "changing" one of its fields really means constructing a new object and swapping it in, often with set.
• Searching a list of objects for a match on multiple fields at once (row and col together, never either alone) is worth double-checking any time similar-but-not-identical data could exist side by side in the same collection.