GridPath: 2024 FRQ 4

Tracing a path through a grid of numbers, always stepping toward whichever neighboring value is smaller, is the puzzle behind this AP Computer Science A free-response question — first figuring out which single neighbor to step to, then following that step over and over until the path runs out of grid.

What This FRQ Tests

• AP CSA units: Unit 8 (2D Array) and Unit 4 (Iteration)
• Core skill: checking whether a 2D array neighbor exists before reading it, to avoid stepping off the edge of the grid
• Secondary skill: repeatedly calling a helper method to walk a path until a stopping condition is reached, accumulating a result along the way
• Official category: "2D Array" — always FRQ 4 on the AP CSA exam

The Setup

• A given Location class (not modified) simply stores a row and column:
  • int getRow() and int getCol() — getters for the stored position
• GridPath holds:
  • private int[][] grid — filled with distinct values that never change
• You're asked to write two methods:
  • Location getNextLoc(int row, int col) — finds the smaller of the two "next" neighbors (right and below)
  • int sumPath(int row, int col) — follows repeated calls to getNextLoc and totals every value visited

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

The Rule, Broken Down

1. Only two neighbors are ever considered: the element directly below, and the element directly to the right.
2. If both exist, return the Location of whichever one has the smaller value (values are guaranteed never equal).
3. If only one of the two exists (because the given position is in the last row or last column, but not both), return that one.
4. The method is never called on the very last row and last column at the same time — that position has neither neighbor.

Step-by-Step Approach

1. Figure out whether a right neighbor exists: is col + 1 still a valid column index?
2. Figure out whether a below neighbor exists: is row + 1 still a valid row index?
3. If both exist, compare grid[row][col + 1] to grid[row + 1][col] and return the smaller one's Location.
4. If only the right neighbor exists, return its Location.
5. Otherwise (only the below neighbor exists), return its Location.

The Code

public Location getNextLoc(int row, int col)
{
    boolean hasRight = col + 1 < grid[row].length;
    boolean hasBelow = row + 1 < grid.length;

    if (hasRight && hasBelow)
    {
        if (grid[row][col + 1] < grid[row + 1][col])
        {
            return new Location(row, col + 1);
        }
        else
        {
            return new Location(row + 1, col);
        }
    }
    else if (hasRight)
    {
        return new Location(row, col + 1);
    }
    else
    {
        return new Location(row + 1, col);
    }
}

Why Each Piece Matters

• col + 1 < grid[row].length — checks against the row's length (the number of columns), since we're asking whether one more column exists in this specific row.
• row + 1 < grid.length — checks against the 2D array's overall length (the number of rows), since we're asking whether one more row exists at all.
• Computing both booleans up front, before branching — this keeps the three-way decision (both exist / only right / only below) clean, rather than nesting the existence checks inside each other.
• The final else covers "only below exists" without needing to explicitly test for it — since the method's precondition guarantees at least one neighbor always exists, ruling out "both" and "only right" leaves exactly one possibility.

Tracing the Example

Using the 5×5 grid from the question:

All four results match the question's explanations exactly.

Common Mistakes to Avoid

• Swapping which array dimension each existence check uses — hasRight needs grid[row].length (columns), while hasBelow needs grid.length (rows); mixing them up either misses a valid neighbor or reads past the array's bounds.
• Comparing values without first confirming both neighbors exist. Reading grid[row + 1][col] when there is no next row throws an ArrayIndexOutOfBoundsException.
• Getting the comparison direction backwards — the rule wants the smaller value's Location, so double check which branch returns which neighbor.

Part (b): Writing sumPath(int row, int col)

The Rule, Broken Down

1. Start at (row, col) and add its value to a running total.
2. Repeatedly call getNextLoc to find the next position, move there, and add its value too.
3. Stop once the path reaches the element in the very last row and last column of grid — but still include that final element's value in the total.

Step-by-Step Approach

1. Start the running sum with the value at the given starting position.
2. Figure out the index of the last row and the last column once, up front.
3. Loop for as long as the current position is not both the last row and last column.
4. Each iteration: call getNextLoc on the current position, move to that new position, and add its value to the sum.
5. Once the loop condition fails (the last cell has just been reached and its value already added), return the sum.

The Code

public int sumPath(int row, int col)
{
    int sum = grid[row][col];
    int lastRow = grid.length - 1;
    int lastCol = grid[0].length - 1;

    while (row != lastRow || col != lastCol)
    {
        Location next = getNextLoc(row, col);
        row = next.getRow();
        col = next.getCol();
        sum = sum + grid[row][col];
    }

    return sum;
}

Why Each Piece Matters

• sum starts at grid[row][col] — the starting element itself is part of the path and needs to be counted, not just the elements visited afterward.
• row != lastRow || col != lastCol — the loop needs to keep going as long as either coordinate hasn't reached the last one yet; using && instead would end the loop too early, the moment just one of the two coordinates matched.
• Reusing getNextLoc instead of re-deriving neighbor logic — the problem explicitly says to assume it works correctly and use it, which also means any bug in your own getNextLoc doesn't cascade into sumPath's scoring on the real exam.
• Adding grid[row][col] after updating row and col — the sum needs the new position's value each time, not the one just left behind.

Tracing the Example

Using the question's second grid and sumPath(1, 1):

Position (3, 4) is the last row and last column (a 4×5 grid has rows 0–3 and columns 0–4), so the loop stops there. Final sum: 19 — matches the question exactly.

Common Mistakes to Avoid

• Forgetting to include the starting element's value. The path begins at (row, col), not one step after it.
• Using && instead of || in the stopping condition. This would end the path as soon as either the row or column coordinate alone matched the last one, even if the other hadn't caught up yet.
• Adding the value for the old position instead of the new one after each call to getNextLoc — the sum should reflect the path actually walked, one new cell at a time.
• Re-implementing the neighbor-finding logic inline instead of calling getNextLoc — this duplicates work and ignores the "must use getNextLoc appropriately" requirement.

Key Takeaways

• Checking whether a 2D array neighbor exists means comparing against the right dimension's length — grid[row].length for columns, grid.length for rows — never assume they're interchangeable.
• A "stop only when both coordinates match a target" condition needs || in the loop's continue-condition, since either coordinate alone not matching yet means the path isn't finished.
• Once a helper method is written and trusted, later methods should call it repeatedly to walk a structure, rather than duplicating its logic inline.