2D Arrays Pt 2 HW
Popcorn Hack 1
Farmer John has 7 cats. They all eat a certain amount of magical grass, measured in lbs, every day. The farmer makes a 2D array with information about how much grass each cat ate each day. Each row represents how many pounds each cat ate that day. Each column represents a single cat. Please return a 1D array, where each element is the total amount of grass the cat ate.
TL;DR: Sum up the values within each column and return a 1D array.
// Sample test case
int[][] grassData = {
{2, 3, 1, 4, 3, 2, 5},
{1, 2, 3, 1, 4, 2, 3},
{3, 4, 2, 5, 1, 3, 2}
};
// Your Code Here
// Expected Output: [6, 9, 6, 10, 8, 7, 10]
public class Main {
public static void main(String[] args) {
int[][] grassData = {
{2, 3, 1, 4, 3, 2, 5},
{1, 2, 3, 1, 4, 2, 3},
{3, 4, 2, 5, 1, 3, 2}
};
int total = 0;
for (int[] row : grassData) {
for (int item: row) {
total += item;
}
}
System.out.println(total);
}
}
Main.main(null);
56
HW
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:
- getTotalGrass()
- Return total sum of all “tastiness values” from the pastures in the 2D array
- 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.)
- 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.
EC
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 {
/** The 2D grid of pasture tastineess 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() {
/* Code below */
}
/**
* Returns max sum of tastiness of a square in the 2D array (square can be 1x1, 2x2, etc.)
*/
public int maxSquare() {
/* Code below */
}
/**
* Returns the maximum tastiness sum subarray in the flattened 2D grid
*/
public int maxSubarraySum() {
/* Code below */
}
}
int[][] pastures = {
{-3, 6, -1},
{2, -1, 5},
{-9, 4, -1}
};
GrassPasture gp = new GrassPasture(pastures);
System.out.println("Total Tastiness: " + gp.getTotalGrass());
// answer should be -2
System.out.println("Max Square Sum: " + gp.maxSquare());
// answer should be 9
System.out.println("Max Subarray Sum: " + gp.maxSubarraySum());
// answer should be 11
// If you are interested in the extra credit, you can answer below:
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 rows = pastures.length;
int cols = pastures[0].length;
int[][] dp = new int[rows + 1][cols + 1];
int maxSum = Integer.MIN_VALUE;
// Precompute prefix sums for efficient square sum calculation
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
dp[i][j] = pastures[i - 1][j - 1]
+ dp[i - 1][j]
+ dp[i][j - 1]
- dp[i - 1][j - 1];
}
}
// Iterate through all possible square sizes
for (int size = 1; size <= Math.min(rows, cols); size++) {
for (int i = size; i <= rows; i++) {
for (int j = size; j <= cols; j++) {
int squareSum = dp[i][j]
- dp[i - size][j]
- dp[i][j - size]
+ dp[i - size][j - size];
maxSum = Math.max(maxSum, squareSum);
}
}
}
return maxSum;
}
/**
* Returns the maximum tastiness sum subarray in the flattened 2D grid
*/
public int maxSubarraySum() {
int[] flattened = new int[pastures.length * pastures[0].length];
int index = 0;
for (int[] row : pastures) {
for (int value : row) {
flattened[index++] = value;
}
}
// Apply Kadane's Algorithm on the flattened array
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
for (int value : flattened) {
currentSum = Math.max(value, currentSum + value);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
public static void main(String[] args) {
int[][] pastures = {
{-3, 6, -1},
{2, -1, 5},
{-9, 4, -1}
};
GrassPasture gp = new GrassPasture(pastures);
System.out.println("Total Tastiness: " + gp.getTotalGrass());
System.out.println("Max Square Sum: " + gp.maxSquare());
System.out.println("Max Subarray Sum: " + gp.maxSubarraySum());
}
}
GrassPasture.main(null);
Total Tastiness: 2
Max Square Sum: 9
Max Subarray Sum: 11
getTotalGrass():
- Traverses the 2D array, summing all elements.
- Time Complexity: O(N × M), where N and M are the number of rows and columns.
maxSquare():
- Uses dynamic programming to calculate prefix sums for efficient square sum computation.
- Iterates over all possible square sizes and computes the sum using prefix sums.
- Time Complexity: O(N × M × min(N, M)).
- Extra Credit 1: This approach is efficient, but further optimizations for specific constraints might improve it.
- Extra Credit 2: Achieving O(N × M) involves advanced optimization, such as dynamic programming with constraints on valid square growth.
maxSubarraySum():
- Flattens the 2D array into a 1D array and applies Kadane’s algorithm.
- Time Complexity: O(N × M), since flattening and Kadane’s algorithm are linear in complexity.
- Extra Credit 3: Kadane’s algorithm is optimal for finding the maximum subarray sum.
- Extra Credit 4: O(N × M) is the optimal complexity for this problem.