2023 AP® Computer Science A FRQ 4 — BoxOfCandy (2D Arrays)

2023 AP® Computer Science A FRQ 4 — BoxOfCandy (2D Arrays)

Topic: 2D array traversal, null checking, bottom-up search
2025 Curriculum Alignment: Unit 4 (Data Collection — 2D Arrays)

Question

This question involves pieces of candy in a box. The Candy class represents a single piece of candy.

public class Candy {
    /** Returns a String representing the flavor of this piece of candy */
    public String getFlavor() {
        /* implementation not shown */
    }
    
    // There may be instance variables, constructors, and methods that are not shown.
}

The BoxOfCandy class represents a candy box where the candy is arranged in a rectangular grid. The instance variable of the class, box, is a rectangular two-dimensional array of Candy objects. A location in the candy box may contain a piece of candy or may be empty. A piece of candy is represented by a Candy object. An empty location is represented by null.

You will write two methods of the BoxOfCandy class.

Provided Class

public class BoxOfCandy {
    /** box contains at least one row and is initialized in the constructor. */
    private Candy[][] box;
    
    /**
     * Moves one piece of candy in column col, if necessary and possible, so that the box
     * element in row 0 of column col contains a piece of candy, as described in part (a).
     * Returns false if there is no piece of candy in column col and returns true otherwise.
     * Precondition: col is a valid column index in box.
     */
    public boolean moveCandyToFirstRow(int col) {
        /* to be implemented in part (a) */
    }
    
    /**
     * Removes from box and returns a piece of candy with flavor specified by the parameter, or
     * returns null if no such piece is found, as described in part (b)
     */
    public Candy removeNextByFlavor(String flavor) {
        /* to be implemented in part (b) */
    }
    
    // There may be instance variables, constructors, and methods that are not shown.
}

Part (a)

Write the moveCandyToFirstRow method, which attempts to ensure that the box element at row 0 and column col contains a piece of candy, using the following steps:

  • If the element at row 0 and column col already contains a piece of candy, then box is unchanged and the method returns true.
  • If the element at row 0 and column col does not contain a piece of candy, then the method searches the remaining rows of column col for a piece of candy. If a piece of candy can be found in column col, it is moved to row 0, its previous location is set to null, and the method returns true; otherwise, the method returns false.

Example: The grid represents the contents of box. An empty square is null. A non-empty square contains a Candy object with the flavor shown.

lime
orange
cherry

moveCandyToFirstRow(0) returns false because row 0, column 0 does not contain candy and there are no pieces of candy in column 0. Contents unchanged.

moveCandyToFirstRow(1) returns true because row 0, column 1 already contains a piece of candy. Contents unchanged.

moveCandyToFirstRow(2) moves one of the two pieces of candy in column 2 to row 0 of column 2, sets the previous location to null, and returns true. The result could be either:

Option 1
lime orange
cherry
Option 2
lime cherry
orange

Complete the moveCandyToFirstRow method.

Part (b)

Write the removeNextByFlavor method, which attempts to remove and return one piece of candy from the box. The piece of candy to be removed is the first piece of candy with a flavor equal to the parameter flavor that is encountered while traversing the candy box in the following order: the last row of the box is traversed from left to right, then the next-to-last row is traversed from left to right, etc., until either a piece of candy with the desired flavor is found or the entire candy box has been searched.

If the removeNextByFlavor method finds a Candy object with the desired flavor, the corresponding box element is assigned null, all other box elements are unchanged, and the removed Candy object is returned. Otherwise, box is unchanged and the method returns null.

Example: The following grid shows the contents of box before any method calls:

lime orange
lime
cherry lime

removeNextByFlavor("cherry") removes and returns the Candy object at row 2, column 0:

lime orange
lime
lime

removeNextByFlavor("lime") removes and returns the Candy object at row 2, column 2 (first lime encountered from bottom-left):

lime orange
lime

removeNextByFlavor("grape") returns null because no grape-flavored candy is found. Contents unchanged.

Complete the removeNextByFlavor method.

Solution & Explanation

Part (a) Solution

public boolean moveCandyToFirstRow(int col) {
    // If row 0 already has candy, return true
    if (box[0][col] != null) {
        return true;
    }
    
    // Search remaining rows for candy
    for (int row = 1; row < box.length; row++) {
        if (box[row][col] != null) {
            // Move candy to row 0
            box[0][col] = box[row][col];
            box[row][col] = null;
            return true;
        }
    }
    
    // No candy found in this column
    return false;
}

Part (a) Explanation

Algorithm Logic:

  1. Check row 0: If box[0][col] is not null, candy already exists there → return true
  2. Search rows 1 through last row: Look for first non-null candy in column col
  3. If candy found:
    • Move it to box[0][col]
    • Set original location to null
    • Return true
  4. If no candy found: Return false

Key Points:

  • Must check for null using != null or == null
  • Start search at row 1 (row 0 already checked)
  • Move FIRST candy found, then return immediately (don't continue searching)
  • box.length gives number of rows
  • box[row].length would give number of columns (not needed here)

Part (b) Solution

public Candy removeNextByFlavor(String flavor) {
    // Start from last row and work upward
    for (int row = box.length - 1; row >= 0; row--) {
        // Traverse each row left to right
        for (int col = 0; col < box[row].length; col++) {
            // Check if there's candy at this location
            if (box[row][col] != null) {
                // Check if flavor matches
                if (box[row][col].getFlavor().equals(flavor)) {
                    Candy candyToReturn = box[row][col];
                    box[row][col] = null;
                    return candyToReturn;
                }
            }
        }
    }
    
    // No candy with matching flavor found
    return null;
}

Part (b) Explanation

Algorithm Logic:

  1. Outer loop: Traverse rows from bottom to top (box.length - 1 down to 0)
  2. Inner loop: Traverse each row left to right (0 to box[row].length - 1)
  3. For each position:
    • Check if position is not null
    • If not null, check if flavor matches using getFlavor().equals(flavor)
    • If match found:
      • Save reference to the Candy object
      • Set position to null
      • Return the saved Candy object
  4. If loop completes: No matching candy found, return null

Traversal Order Visual:

For a 3×4 grid, the traversal order is:

9 10 11 12
5 6 7 8
1 2 3 4

Important Details:

  • Null checking is critical: Always check box[row][col] != null before calling getFlavor()
  • String comparison: Use .equals(), NOT ==
  • Return the object before setting to null: Must save reference first
  • Nested loop structure: Outer loop = rows (backward), inner loop = columns (forward)

Example Walkthrough

Given this box and calling removeNextByFlavor("lime"):

lime (0,1) orange
lime (1,3)
cherry lime (2,2)

Search order:

  1. Row 2, Col 0: cherry (not lime, continue)
  2. Row 2, Col 1: null (skip)
  3. Row 2, Col 2: lime ← FOUND! Remove and return this

The lime at (2,2) is returned first because it's encountered first in the bottom-up, left-to-right traversal.

Scoring Notes

Part (a) — 4 points:

  • +1: Checks if box[0][col] contains candy (not null)
  • +1: Searches remaining rows of column col
  • +1: Moves candy correctly and sets old location to null
  • +1: Returns correct boolean value

Part (b) — 5 points:

  • +1: Accesses all elements of box in correct order (bottom row first, left to right)
  • +1: Checks if element is not null before accessing flavor
  • +1: Compares flavor correctly using .equals()
  • +1: Sets found element to null
  • +1: Returns correct value (Candy object or null)

Common Mistakes to Avoid:

  • Part (a): Not returning immediately after moving first candy found
  • Part (a): Forgetting to set old location to null after moving candy
  • Part (a): Starting search at row 0 instead of row 1
  • Part (b): Traversing top-to-bottom instead of bottom-to-top
  • Part (b): Not checking for null before calling getFlavor() (causes NullPointerException)
  • Part (b): Using == instead of .equals() for String comparison
  • Part (b): Setting to null before saving reference (would return null instead of Candy)

College Board Resources

Contact form