Computer Science A

Course Progress 0/0
Sprint View
Week 19 2018 FRQ Question 4

2018 FRQ Question 4

12 min read

Question Overview

This question involves reasoning about arrays of integers. You will write two static methods, both of which are in a class named ArrayTester.

ArrayTester Class Structure

The class provides several methods for working with 2D arrays:

  • Part (a): getColumn - Extract a column from a 2D array
  • Part (b): isLatin - Determine if a 2D array is a Latin square
  • Helper methods (provided): hasAllValues and containsDuplicates
public class ArrayTester
{
    /** Returns an array containing the elements of column c of arr2D in the same order as
     * they appear in arr2D.
     * Precondition: c is a valid column index in arr2D.
     * Postcondition: arr2D is unchanged.
     */
    public static int[] getColumn(int[][] arr2D, int c)
    { /* to be implemented in part (a) */ }

    /** Returns true if and only if every value in arr1 appears in arr2.
     * Precondition: arr1 and arr2 have the same length.
     * Postcondition: arr1 and arr2 are unchanged.
     */
    public static boolean hasAllValues(int[] arr1, int[] arr2)
    { /* implementation not shown */ }

    /** Returns true if arr contains any duplicate values;
     * false otherwise.
     */
    public static boolean containsDuplicates(int[] arr)
    { /* implementation not shown */ }

    /** Returns true if square is a Latin square as described in part (b);
     * false otherwise.
     * Precondition: square has an equal number of rows and columns.
     * square has at least one row.
     */
    public static boolean isLatin(int[][] square)
    { /* to be implemented in part (b) */ }
}

Part (a): getColumn Method

Task

Write a static method getColumn, which returns a one-dimensional array containing the elements of a single column in a two-dimensional array.

Requirements

  • The elements in the returned array should be in the same order as they appear in the given column
  • The notation arr2D[r][c] represents the array element at row r and column c
  • The original 2D array must remain unchanged

Example

Given this 2D array:

int[][] arr2D = { { 0, 1, 2 },
                  { 3, 4, 5 },
                  { 6, 7, 8 },
                  { 9, 5, 3 } };

Calling ArrayTester.getColumn(arr2D, 1) should return: {1, 4, 7, 5}

Visual representation:

     Column 0  Column 1  Column 2
Row 0:   0        [1]       2
Row 1:   3        [4]       5
Row 2:   6        [7]       8
Row 3:   9        [5]       3
                   ↓
            Result: {1, 4, 7, 5}

Code Runner Challenge

2D Arrays — Extract Column (Starter Code)

View IPYNB Source 
// CODE_RUNNER: 2D Arrays — Extract Column (Starter Code)

public class Main {

    /** Returns an array containing the elements of column c of arr2D
     *  in the same order as they appear in arr2D.
     *  Precondition: c is a valid column index in arr2D.
     *  Postcondition: arr2D is unchanged.
     */
    public static int[] getColumn(int[][] arr2D, int c) {
        int[] result = new int[arr2D.length];
        
        for (int r = 0; r < arr2D.length; r++) {
            result[r] = arr2D[r][c];
        }
        
        return result;
    }

    // Driver (do not modify)
    public static void main(String[] args) {
        int[][] arr2D = {
            { 0, 1, 2 },
            { 3, 4, 5 },
            { 6, 7, 8 },
            { 9, 5, 3 }
        };

        System.out.println("Testing getColumn for column 1:");
        int[] result = getColumn(arr2D, 1);
        System.out.print("Result: {");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
            if (i < result.length - 1) System.out.print(", ");
        }
        System.out.println("}");
        System.out.println("Expected: {1, 4, 7, 5}");
    }
}
Main.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Solution Explanation - Part (a)

Step-by-step breakdown:

Step 1: Create result array with the correct size (number of rows):

int[] result = new int[arr2D.length];
  • arr2D.length gives the number of rows

Step 2: Iterate through each row and extract the element at column c:

for (int r = 0; r < arr2D.length; r++) {
    result[r] = arr2D[r][c];
}
  • For each row r, get arr2D[r][c] (the element at row r, column c)
  • Store it in result[r]

Step 3: Return the result array:

return result;

Key concepts:

  • The number of rows = arr2D.length
  • Accessing an element: arr2D[row][column]
  • The original array is not modified (we only read from it)

Part (b): isLatin Method

What is a Latin Square?

A two-dimensional square array of integers is a Latin square if ALL of the following conditions are true:

  1. The first row has no duplicate values
  2. All values in the first row appear in each row of the square
  3. All values in the first row appear in each column of the square

Examples of Latin Squares

Example 1: 3×3 Latin Square

1  2  3
2  3  1
3  1  2
  • First row: {1, 2, 3} - no duplicates ✓
  • Each row contains {1, 2, 3} ✓
  • Each column contains {1, 2, 3} ✓

Example 2: 4×4 Latin Square

10  30  20   0
 0  20  30  10
30   0  10  20
20  10   0  30
  • First row: {10, 30, 20, 0} - no duplicates ✓
  • Each row contains {10, 30, 20, 0} ✓
  • Each column contains {10, 30, 20, 0} ✓

Examples that are NOT Latin Squares

Not a Latin Square - Duplicate in first row:

1  2  1  ← First row has duplicate value (1 appears twice)
2  1  1
1  1  2

Not a Latin Square - Missing values in a row:

1  2  3
3  1  2
7  8  9  ← Third row doesn't contain all values from first row

Not a Latin Square - Missing values in columns:

1  2
1  2  ← Each column is {1, 1} and {2, 2}, not {1, 2}

Helper Methods (Provided)

You have access to these helper methods:

  1. containsDuplicates(int[] arr)
    • Returns true if the array contains any duplicate values
    • Returns false otherwise
  2. hasAllValues(int[] arr1, int[] arr2)
    • Returns true if and only if every value in arr1 appears in arr2
    • Precondition: arr1 and arr2 have the same length
  3. getColumn(int[][] arr2D, int c)
    • Returns a 1D array containing the elements of column c
    • You wrote this in part (a)

Requirements for Part (b)

You MUST use getColumn, hasAllValues, and containsDuplicates appropriately to receive full credit.

Code Runner Challenge

2D Arrays — Latin Square Checker (Starter Code)

View IPYNB Source 
// CODE_RUNNER: 2D Arrays — Latin Square Checker (Starter Code)

public class Main {

    // Helper method from Part (a)
    public static int[] getColumn(int[][] arr2D, int c) {
        int[] result = new int[arr2D.length];
        for (int r = 0; r < arr2D.length; r++) {
            result[r] = arr2D[r][c];
        }
        return result;
    }

    // Helper method - checks if every value in arr1 appears in arr2
    public static boolean hasAllValues(int[] arr1, int[] arr2) {
        for (int value : arr1) {
            boolean found = false;
            for (int element : arr2) {
                if (value == element) {
                    found = true;
                    break;
                }
            }
            if (!found) return false;
        }
        return true;
    }

    // Helper method - checks if array contains duplicates
    public static boolean containsDuplicates(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] == arr[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    /** Returns true if square is a Latin square;
     *  false otherwise.
     *  Precondition: square has an equal number of rows and columns.
     *                square has at least one row.
     */
    public static boolean isLatin(int[][] square) {
        // Check if first row has duplicates
        if (containsDuplicates(square[0])) {
            return false;
        }

        // Check if all rows have the same values as the first row
        for (int r = 1; r < square.length; r++) {
            if (!hasAllValues(square[0], square[r])) {
                return false;
            }
        }

        // Check if all columns have the same values as the first row
        for (int c = 0; c < square[0].length; c++) {
            if (!hasAllValues(square[0], getColumn(square, c))) {
                return false;
            }
        }

        return true;
    }

    // Driver (do not modify)
    public static void main(String[] args) {
        // Test Case 1: Valid Latin Square
        int[][] latin1 = {
            {1, 2, 3},
            {2, 3, 1},
            {3, 1, 2}
        };
        System.out.println("Test 1 (Valid Latin Square):");
        System.out.println("Result: " + isLatin(latin1));
        System.out.println("Expected: true");

        // Test Case 2: Valid Latin Square (4x4)
        int[][] latin2 = {
            {10, 30, 20, 0},
            {0, 20, 30, 10},
            {30, 0, 10, 20},
            {20, 10, 0, 30}
        };
        System.out.println("Test 2 (Valid Latin Square 4x4):");
        System.out.println("Result: " + isLatin(latin2));
        System.out.println("Expected: true");

        // Test Case 3: Invalid - Duplicate in first row
        int[][] notLatin1 = {
            {1, 2, 1},
            {2, 1, 1},
            {1, 1, 2}
        };
        System.out.println("Test 3 (Duplicate in first row):");
        System.out.println("Result: " + isLatin(notLatin1));
        System.out.println("Expected: false");

        // Test Case 4: Invalid - Missing value in row
        int[][] notLatin2 = {
            {1, 2, 3},
            {3, 1, 2},
            {7, 8, 9}
        };
        System.out.println("Test 4 (Missing values in row):");
        System.out.println("Result: " + isLatin(notLatin2));
        System.out.println("Expected: false");

        // Test Case 5: Invalid - Missing value in column
        int[][] notLatin3 = {
            {1, 2},
            {1, 2}
        };
        System.out.println("Test 5 (Missing values in column):");
        System.out.println("Result: " + isLatin(notLatin3));
        System.out.println("Expected: false");
    }
}
Main.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Solution Explanation - Part (b)

Step-by-step breakdown:

Step 1: Check if the first row has duplicates

if (containsDuplicates(square[0])) {
    return false;
}
  • square[0] is the first row
  • If it has duplicates, it can’t be a Latin square

Step 2: Check if each row has all values from the first row

for (int r = 1; r < square.length; r++) {
    if (!hasAllValues(square[0], square[r])) {
        return false;
    }
}
  • Loop through rows 1 to the last row (skip row 0 since we’re comparing to it)
  • hasAllValues(square[0], square[r]) checks if every value in the first row appears in row r
  • If any row is missing values from the first row, return false

Step 3: Check if each column has all values from the first row

for (int c = 0; c < square[0].length; c++) {
    if (!hasAllValues(square[0], getColumn(square, c))) {
        return false;
    }
}
  • Loop through all columns (0 to number of columns - 1)
  • getColumn(square, c) extracts column c as a 1D array
  • hasAllValues(square[0], getColumn(square, c)) checks if every value in the first row appears in column c
  • If any column is missing values from the first row, return false

Step 4: All checks passed

return true;
  • If we made it through all checks, it’s a valid Latin square

Key Insights

  1. Order matters: First check for duplicates, then check rows, then check columns
  2. Use helper methods: The solution requires using containsDuplicates, hasAllValues, and getColumn
  3. Early return: As soon as any condition fails, return false immediately
  4. Row vs Column access:
    • Rows: square[r] gives you the entire row
    • Columns: Must use getColumn(square, c) to extract a column

Scoring Guidelines (AP Official)

Part (a): getColumn — 3 points

Intent: Create and return a one-dimensional array containing the elements of a specified column from a two-dimensional array.

  • +1 point: Declares and initializes the result array with the correct length
    • Must use arr2D.length (number of rows) as the size
  • +1 point: Accesses all elements in column c
    • Must iterate through all rows
    • Must access arr2D[r][c] for each row r
  • +1 point: Returns an array with the correct elements in the correct order
    • Elements must be in the same order as they appear in the column
    • Must return the array (not print it)

Sample Solution:

public static int[] getColumn(int[][] arr2D, int c) {
    int[] result = new int[arr2D.length];
    for (int r = 0; r < arr2D.length; r++) {
        result[r] = arr2D[r][c];
    }
    return result;
}

Part (b): isLatin — 6 points

Intent: Determine whether a two-dimensional square array is a Latin square using provided helper methods.

  • +1 point: Calls containsDuplicates on the first row
    • Must check containsDuplicates(square[0])
  • +1 point: Uses the result of containsDuplicates to determine if the first row has duplicates
    • If true (has duplicates), should return false or continue checking
  • +1 point: Calls hasAllValues for each row (or all but the first row)
    • Must compare first row to other rows using hasAllValues
    • Must check all rows in a loop
  • +1 point: Calls getColumn for each column
    • Must extract each column using getColumn(square, c) in a loop
  • +1 point: Calls hasAllValues for each column
    • Must compare first row to each column using hasAllValues(square[0], getColumn(square, c))
    • Must check all columns in a loop
  • +1 point: Returns correct boolean value
    • Returns true only if all three conditions are met (no duplicates in first row, all rows have same values, all columns have same values)
    • Returns false if any condition fails

Sample Solution:

public static boolean isLatin(int[][] square) {
    if (containsDuplicates(square[0])) {
        return false;
    }
    
    for (int r = 1; r < square.length; r++) {
        if (!hasAllValues(square[0], square[r])) {
            return false;
        }
    }
    
    for (int c = 0; c < square[0].length; c++) {
        if (!hasAllValues(square[0], getColumn(square, c))) {
            return false;
        }
    }
    
    return true;
}

Common Mistakes to Avoid

Part (a):

  • Using arr2D[0].length instead of arr2D.length for the result array size
  • Accessing elements as arr2D[c][r] instead of arr2D[r][c]
  • Modifying the original array
  • Not returning the result array

Part (b):

  • Not using all three required helper methods (containsDuplicates, hasAllValues, getColumn)
  • Forgetting to check if the first row has duplicates
  • Only checking some rows or columns instead of all of them
  • Comparing rows/columns to each other instead of to the first row
  • Not calling getColumn to extract columns before checking them

Course Timeline