Problem Brief

Largest Sub-Grid

FULLTIMEOA

Given a square integer matrix grid and an integer maxSum, find the maximum side length of a square sub-grid whose total sum is at most maxSum.

If no square sub-grid satisfies the condition, return 0.

1Example 1

Input

grid = [[2, 2, 2], [3, 3, 3], [4, 4, 4]], maxSum = 4

Output

Explanation

Every 1 x 1 square in the last row sums to 4, but no larger square stays within the limit. Under the prompt's example, the maximum valid size is 0.

Constraints

Limits and guarantees your solution can rely on.

grid is an n x n matrix
1 <= n <= 300
1 <= maxSum <= 10^9

Draft autosaves locally

public int largestSubGrid(int[][] grid, int maxSum) {
  // write your code here
}

Input

grid

[[2, 2, 2], [3, 3, 3], [4, 4, 4]]

maxSum

Output