Period 3 2D Arrays Pt 2 - Homework

Problem

Farmer John has a rectangular grass pasture with N rows and M columns for the cows to graze on. Each pasture has a certain tastiness value. However, the gen alpha Bessie has gotten quite picky with what she eats.

Given a 2D array (template below) with size NxM, please write functions for the following:

1. getTotalGrass()
   • Return total sum of all “tastiness values” from the pastures in the 2D array
2. maxSquare()
   • Because Bessie sometimes likes enjoying square grass patches, she wants to find the best one.
   • Returns the maximum sum of tastiness value of a square in the 2D array. (Square could be 1x1, 2x2, 3x3, etc.)
3. maxSubarraySum()
   • Sometimes, Bessie enjoys eating grass in a line.
   • Return the maximum sum of a continuous subarray in this array if it was “flattened” to be a 1D array. In other words, make the 2D array into a 1D array by combining all rows and find the max subarray sum.

For an example case, see below in the code.

Extra Credit Opportunities

Extra Credit 1 (+0.01): What is the time complexity of your maxSquare code? Explain.

Extra Credit 2 (+0.01): This is achieved if you get the optimal complexity for maxPatch.

Extra Credit 3 (+0.01): What is the time complexity of your maxSubarraySum code? Explain.

Extra Credit 4 (+0.01): This is achieved if you get the optimal complexity for maxSubarraySum.

public class GrassPasture {
    private int[][] tastinessGrid;

    public GrassPasture(int[][] tastinessGrid) {
        this.tastinessGrid = tastinessGrid;
    }

    /**
     * Returns the total sum of all tastiness values in the 2D pasture grid.
     * 
     * Time Complexity: O(N * M)
     * - We iterate over every cell in the 2D grid once, summing all values.
     */
    public int getTotalGrass() {
        int total = 0;
        for (int[] row : tastinessGrid) {
            for (int value : row) {
                total += value;
            }
        }
        return total;
    }

    /**
     * Finds the maximum sum of tastiness values in a square submatrix (NxN).
     * 
     * Time Complexity: O(N^3)
     * - We iterate over all possible square sizes (O(min(N, M))).
     * - For each square size, we iterate over all possible top-left corners (O(N * M)).
     * - Then, we sum all elements in the square (O(N^2) in the worst case).
     * - Overall, this results in O(N^3) complexity.
     * 
     * Optimal Complexity for Extra Credit: O(N^2) using prefix sums or dynamic programming.
     */
    public int maxSquare() {
        int rows = tastinessGrid.length;
        int cols = tastinessGrid[0].length;
        int maxSum = Integer.MIN_VALUE;

        for (int size = 1; size <= Math.min(rows, cols); size++) {
            for (int startX = 0; startX <= rows - size; startX++) {
                for (int startY = 0; startY <= cols - size; startY++) {
                    int squareSum = 0;
                    for (int x = startX; x < startX + size; x++) {
                        for (int y = startY; y < startY + size; y++) {
                            squareSum += tastinessGrid[x][y];
                        }
                    }
                    maxSum = Math.max(maxSum, squareSum);
                }
            }
        }
        return maxSum;
    }

    /**
     * Finds the maximum sum of a contiguous subarray when the 2D pasture is flattened.
     * 
     * Time Complexity: O(N * M)
     * - We iterate over all elements to flatten the 2D grid (O(N * M)).
     * - We then apply a modified prefix sum algorithm (O(N * M)).
     * - Overall, this results in O(N * M) complexity.
     * 
     * Optimal Complexity for Extra Credit: O(N * M), which is already achieved.
     */
    public int maxSubarraySum() {
        int rows = tastinessGrid.length;
        int cols = tastinessGrid[0].length;
        int[] flattenedGrid = new int[rows * cols];
        int index = 0;

        for (int[] row : tastinessGrid) {
            for (int value : row) {
                flattenedGrid[index++] = value;
            }
        }

        return maxSubarraySumWithPrefix(flattenedGrid);
    }

    /**
     * Uses a prefix sum approach to find the maximum contiguous subarray sum.
     * 
     * Time Complexity: O(N * M)
     * - We iterate through the 1D array once to compute the max sum.
     * - This results in linear time complexity, O(N * M).
     */
    private int maxSubarraySumWithPrefix(int[] array) {
        int n = array.length;
        int[] prefixSum = new int[n];
        prefixSum[0] = array[0];
        int maxSum = array[0];

        for (int i = 1; i < n; i++) {
            prefixSum[i] = Math.max(array[i], prefixSum[i - 1] + array[i]);
            maxSum = Math.max(maxSum, prefixSum[i]);
        }

        return maxSum;
    }
}