FRQ 4: Successors Class — 2D Array Processing

7 min read

Overview

This question involves reasoning about a two-dimensional (2D) array of integers. You will write two static methods, both of which are in a single enclosing class named Successors. These methods process a 2D integer array that contains consecutive values.

Each of these integers may be in any position in the 2D integer array. For example, the following 2D integer array contains the integers 5 through 16, inclusive:

  0   1   2   3
0 15  5   9   10
1 12  16  11  6
2 14  8   13  7

Learning Objectives

  • Traverse and search a 2D array using nested loops
  • Use the Position object to represent locations in a 2D array
  • Create and populate a 2D array of objects
  • Understand the concept of successive values in an array

Instructions

  • Complete Part A (findPosition) first, then Part B (getSuccessorArray)
  • Run each code cell and verify expected output
  • Complete the combined challenge cell
  • Add screenshots in the placeholder sections

The Position Class

The Position class is used to represent positions in the integer array. The notation (r, c) refers to a Position object with row r and column c.

Part (a): findPosition Method

Write a static method findPosition that takes an integer value and a 2D integer array and returns the position of the integer in the given 2D integer array. If the integer is not an element of the 2D integer array, the method returns null.

Examples:

  • findPosition(8, arr) returns (2, 1) because the value 8 appears in arr at row 2 and column 1
  • findPosition(17, arr) returns null because the value 17 does not appear in arr

Scoring Guidelines (4 points):

  1. Nested loop structure (1 point) - Uses nested loops to traverse the 2D array
  2. Accessing array elements (1 point) - Correctly accesses elements using intArr[r][c]
  3. Comparing and returning Position (1 point) - Returns new Position(r, c) when found
  4. Returning null when not found (1 point) - Returns null outside the loops

Complete the method below:

public class Main {
    
    // Inner Position class
    public static class Position {
        private int row;
        private int col;
        
        public Position(int r, int c) {
            row = r;
            col = c;
        }
        
        public String toString() {
            return "(" + row + "," + col + ")";
        }
    }
    
    /** Returns the position of num in intArr;
     *  returns null if no such element exists in intArr.
     *  Precondition: intArr contains at least one row.
     */
    public static Position findPosition(int num, int[][] intArr) {
        // TODO: Write your solution here
        // Use nested loops to search through the 2D array
        for (int r = 0; r < intArr.length; r++) {
            for (int c = 0; c < intArr[r].length; c++) {
                if (intArr[r][c] == num) {
                    return new Position(r, c);
                }
            }
        }
        return null;
    }
    
    public static void main(String[] args) {
        // Test the 2D array from the problem
        int[][] arr = {
            {15, 5, 9, 10},
            {12, 16, 11, 6},
            {14, 8, 13, 7}
        };
        
        System.out.println("Testing findPosition:");
        System.out.println("findPosition(8, arr): " + findPosition(8, arr));
        System.out.println("Expected: (2,1)");
        System.out.println();
        
        System.out.println("findPosition(17, arr): " + findPosition(17, arr));
        System.out.println("Expected: null");
        System.out.println();
        
        System.out.println("findPosition(15, arr): " + findPosition(15, arr));
        System.out.println("Expected: (0,0)");
        System.out.println();
        
        System.out.println("findPosition(7, arr): " + findPosition(7, arr));
        System.out.println("Expected: (2,3)");
    }
}

Main.main(null);

Screenshot Placeholder — Part A

  • Insert code runner screenshot here

Part A Screenshot Placeholder

Part (b): getSuccessorArray Method

A successor is the next consecutive value in the 2D array. For example, in the 2D array shown above, the successor of 8 is 9, and the successor of 16 is not in the array.

Write a static method getSuccessorArray that takes a 2D integer array and returns a 2D array of Position objects that represent the positions of the successors for each value in the given 2D integer array.

Returned Array Rules:

  • The returned 2D array has the same dimensions as the given 2D integer array
  • The value stored at position (r, c) is:
    • The Position of the successor if it exists in the array
    • null if the successor does not exist in the array

Example Output for the test array:

     0       1       2       3
0  (1,2)   (0,2)   (0,3)   (1,2)
1  (0,3)   null    (1,0)   (2,3)
2  (1,5)   (0,2)   (2,2)   null

Scoring Guidelines (5 points):

  1. Creating result array (1 point) - New 2D Position array with same dimensions
  2. Nested loop structure (1 point) - Traverses the entire 2D array
  3. Calling findPosition correctly (2 points):
    • Passes successor value (intArr[r][c] + 1)
    • Passes the array as second parameter
  4. Storing results (1 point) - Results stored at result[r][c]

Requirements:

  • You must use findPosition appropriately to receive full credit
  • The method creates and returns a new 2D array of Position objects with the same dimensions as the input array

Complete the method below:

public class Main {
    
    // Inner Position class
    public static class Position {
        private int row;
        private int col;
        
        public Position(int r, int c) {
            row = r;
            col = c;
        }
        
        public String toString() {
            return "(" + row + "," + col + ")";
        }
    }
    
    public static Position findPosition(int num, int[][] intArr) {
        for (int r = 0; r < intArr.length; r++) {
            for (int c = 0; c < intArr[r].length; c++) {
                if (intArr[r][c] == num) {
                    return new Position(r, c);
                }
            }
        }
        return null;
    }
    
    /** Returns a 2D array of Position objects where each element represents
     *  the position of the successor for each value in intArr.
     *  If the successor does not exist, the value is null.
     */
    public static Position[][] getSuccessorArray(int[][] intArr) {
        // TODO: Write your solution here
        // Create a 2D array of Position objects with the same dimensions
        Position[][] result = new Position[intArr.length][];
        
        // Iterate through each element
        for (int r = 0; r < intArr.length; r++) {
            result[r] = new Position[intArr[r].length];
            for (int c = 0; c < intArr[r].length; c++) {
                // Find the successor (current value + 1)
                result[r][c] = findPosition(intArr[r][c] + 1, intArr);
            }
        }
        
        return result;
    }
    
    public static void printSuccessorArray(Position[][] arr) {
        System.out.println("Successor Array:");
        for (int r = 0; r < arr.length; r++) {
            for (int c = 0; c < arr[r].length; c++) {
                if (arr[r][c] != null) {
                    System.out.print(arr[r][c] + "\t");
                } else {
                    System.out.print("null\t");
                }
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        // Test the 2D array from the problem
        int[][] arr = {
            {15, 5, 9, 10},
            {12, 16, 11, 6},
            {14, 8, 13, 7}
        };
        
        System.out.println("Original Array:");
        for (int r = 0; r < arr.length; r++) {
            for (int c = 0; c < arr[r].length; c++) {
                System.out.print(arr[r][c] + "\t");
            }
            System.out.println();
        }
        System.out.println();
        
        // Get and print the successor array
        Position[][] successors = getSuccessorArray(arr);
        printSuccessorArray(successors);
    }
}

Main.main(null);

Screenshot Placeholder — Part B

  • Insert code runner screenshot here

Part B Screenshot Placeholder

Combined Challenge

Complete the entire problem from start to finish. Use the test array and verify both methods work correctly together.

public class Successors {
    
    public static class Position {
        private int row;
        private int col;
        
        public Position(int r, int c) {
            row = r;
            col = c;
        }
        
        public String toString() {
            return "(" + row + "," + col + ")";
        }
    }
    
    public static Position findPosition(int num, int[][] intArr) {
        for (int r = 0; r < intArr.length; r++) {
            for (int c = 0; c < intArr[r].length; c++) {
                if (intArr[r][c] == num) {
                    return new Position(r, c);
                }
            }
        }
        return null;
    }
    
    public static Position[][] getSuccessorArray(int[][] intArr) {
        Position[][] result = new Position[intArr.length][];
        
        for (int r = 0; r < intArr.length; r++) {
            result[r] = new Position[intArr[r].length];
            for (int c = 0; c < intArr[r].length; c++) {
                result[r][c] = findPosition(intArr[r][c] + 1, intArr);
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        // Test array with values 5-16
        int[][] testArray = {
            {15, 5, 9, 10},
            {12, 16, 11, 6},
            {14, 8, 13, 7}
        };
        
        System.out.println("=== Part A: Testing findPosition ===");
        System.out.println("Finding position of 8: " + findPosition(8, testArray));
        System.out.println("Finding position of 17: " + findPosition(17, testArray));
        System.out.println("Finding position of 16: " + findPosition(16, testArray));
        System.out.println("Finding position of 5: " + findPosition(5, testArray));
        System.out.println();
        
        System.out.println("=== Part B: Testing getSuccessorArray ===");
        Position[][] successors = getSuccessorArray(testArray);
        
        System.out.println("Successor positions:");
        for (int r = 0; r < successors.length; r++) {
            for (int c = 0; c < successors[r].length; c++) {
                if (successors[r][c] != null) {
                    System.out.print(successors[r][c] + "\t");
                } else {
                    System.out.print("null\t");
                }
            }
            System.out.println();
        }
    }
}

Successors.main(null);

Screenshot Placeholder — Combined

  • Insert code runner screenshot here

Combined Challenge Screenshot Placeholder

Reflection Questions

  1. Why is it important to use findPosition in the getSuccessorArray method?
  2. What happens if you try to find the successor of the largest number in the array?
  3. How would the code change if the 2D array was jagged (rows of different lengths) versus rectangular?
  4. What is the time complexity of findPosition? How could it be optimized?
  5. How would you need to modify the code if you wanted to find predecessors instead of successors?