FastPrep
Problem · Matrix

Largest Sub-Grid

Learn this problem
● MediumMathWorks logoMathWorksFULLTIMEOA

Problem statement

Given a square integer matrix grid and an integer maxSum, find the maximum side length k such that the sum of every k x k square subgrid is at most maxSum.

If no size satisfies this condition, return 0.

Function

largestSubGrid(grid: int[][], maxSum: int) → int

Examples

Example 1

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

Every 1 x 1 square has sum 2, 3, or 4, so size 1 is valid. A 2 x 2 square in the first two rows already has sum 10, so size 2 is invalid. The maximum valid side length is 1.

Constraints

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

More MathWorks problems

drafts saved locally
public int largestSubGrid(int[][] grid, int maxSum) {
  // write your code here
}
grid[[2, 2, 2], [3, 3, 3], [4, 4, 4]]
maxSum4
expected1
checking account