Period 3 2D Arrays Pt 2 - Refresher

2D Array Review

This is a review of 2D Arrays. Please see part 1 of the lesson for more details.

Creation of 2D Array

2D arrays are simply arrays within arrays.

// Declare a 2D array
int[][] array = new int[3][4]; // 3 rows and 4 columns

// Declare and initialize with values
int[][] array = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

Indexing of 2D Array

To index a 2D array, place the row number, followed by the column number.

// Access elements in the array
int value = array[0][1]; // Gets the number in the 1st row and 2nd column
System.out.println(value); // Output: 2

int value2 = array[1][2]; // Gets the number in the 2nd row and 3rd column
System.out.println(value2); // Output: 6

// Whoopsie daisies! Error! This is out of bounds
int value3 = array[20][10];
System.out.println(value3);

Iteration of 2D Array

To iterate through a 2D array:

Row-major order

// For loop: Add 5 to all elements of the array
for (int row = 0; row < array.length; row++) {
    for (int col = 0; col < array[row].length; col++) {
        array[row][col] += 5; // Add 5 to each element
    }
}

// Foreach loop: Output all elements of the array
for (int[] row : array) {
    for (int item : row) {
        System.out.print(item + " ");
    }
    System.out.println(); // Adds a newline after each row
}

Column-major order

for (int col = 0; col < array[0].length; col++) {
    for (int row = 0; row < array.length; row++) {
        System.out.print(array[row][col]);
    }
    System.out.println();
}

Popcorn Hack

To solve this problem, you can iterate through each column and sum up the values. Here’s the code:

int[] totalGrass = new int[grassData[0].length];

for (int col = 0; col < grassData[0].length; col++) {
    for (int row = 0; row < grassData.length; row++) {
        totalGrass[col] += grassData[row][col];
    }
}

System.out.println(Arrays.toString(totalGrass));

// Your Code Here

// Expected Output: [6, 9, 6, 10, 8, 7, 10]

```java
import java.util.Arrays;

public class GrassPasture {
    /** The 2D grid of pasture tastiness values */
    private int[][] pastures;

    /** Constructor initializes the field */
    public GrassPasture(int[][] pastures) {
        this.pastures = pastures;
    }

    /**
     * Returns sum of total tastiness for all values in 2D array
     */
    public int getTotalGrass() {
        int total = 0;
        for (int[] row : pastures) {
            for (int value : row) {
                total += value;
            }
        }
        return total;
    }

    /**
     * Returns max sum of tastiness of a square in the 2D array (square can be 1x1, 2x2, etc.)
     */
    public int maxSquare() {
        int n = pastures.length;
        int m = pastures[0].length;
        int maxSum = Integer.MIN_VALUE;

        for (int size = 1; size <= Math.min(n, m); size++) {
            for (int i = 0; i <= n - size; i++) {
                for (int j = 0; j <= m - size; j++) {
                    int sum = 0;
                    for (int x = 0; x < size; x++) {
                        for (int y = 0; y < size; y++) {
                            sum += pastures[i + x][j + y];
                        }
                    }
                    maxSum = Math.max(maxSum, sum);
                }
            }
        }
        return maxSum;
    }

    /**
     * Returns the maximum tastiness sum subarray in the flattened 2D grid
     */
    public int maxSubarraySum() {
        int n = pastures.length;
        int m = pastures[0].length;
        int maxSum = Integer.MIN_VALUE;

        for (int left = 0; left < m; left++) {
            int[] temp = new int[n];
            for (int right = left; right < m; right++) {
                for (int i = 0; i < n; i++) {
                    temp[i] += pastures[i][right];
                }
                maxSum = Math.max(maxSum, kadane(temp));
            }
        }
        return maxSum;
    }

    /**
     * Kadane's algorithm to find the max subarray sum in a 1D array
     */
    private int kadane(int[] arr) {
        int maxEndingHere = arr[0], maxSoFar = arr[0];
        for (int i = 1; i < arr.length; i++) {
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }

    /**
     * Popcorn Hack: Computes the sum of each column and prints the result
     */
    public void popcornHack() {
        int[] totalGrass = new int[pastures[0].length];

        for (int col = 0; col < pastures[0].length; col++) {
            for (int row = 0; row < pastures.length; row++) {
                totalGrass[col] += pastures[row][col];
            }
        }

        System.out.println(Arrays.toString(totalGrass));
    }

    public static void main(String[] args) {
        int[][] pastures = {
            {-3, 6, -1, 2, 4, 3, 5},
            {2, -1, 5, 3, 2, 1, 4},
            {-9, 4, -1, 5, 2, 3, 1}
        };

        GrassPasture gp = new GrassPasture(pastures);

        System.out.println("Total Tastiness: " + gp.getTotalGrass()); // should be -2
        System.out.println("Max Square Sum: " + gp.maxSquare()); // should be 9
        System.out.println("Max Subarray Sum: " + gp.maxSubarraySum()); // should be 11

        gp.popcornHack(); // Expected Output: [6, 9, 6, 10, 8, 7, 10]
    }
}