FastPrep
Problem · Matrix

Sub-matrix Sums

Learn this problem
● MediumIMCFULLTIMEOA

Problem statement

Given an n x n matrix of integers and an integer threshold, determine the maximum size k of a square sub-matrix such that every k x k sub-matrix has a sum less than or equal to threshold.

Return the largest such k. If every square sub-matrix has a sum greater than threshold, return 0.

Function

maxSize(matrix: int[][], threshold: int) → int

Complete the function maxSize.

  • int[][] matrix: an n x n integer matrix
  • int threshold: the maximum acceptable sum of any square sub-matrix

Return the largest valid square size.

Examples

Example 1

matrix = [[2, 2, 2], [3, 3, 3], [4, 4, 4]]threshold = 3return = 0

The largest sum among the 1 x 1 sub-matrices is 4. Since threshold < 4, no square size satisfies the condition.

1 x 1 sub-matrices

222
333
444
Maximum sum = 4

Example 2

matrix = [[2, 2, 2], [3, 3, 3], [4, 4, 4]]threshold = 4return = 1

Every 1 x 1 sub-matrix has sum at most 4, while the maximum 2 x 2 sum is 14.

2 x 2 sub-matrices

222
333
444
Top left
222
333
444
Top right
222
333
444
Bottom left
222
333
444
Bottom right

The largest 2 x 2 sum is 14.

Example 3

matrix = [[2, 2, 2], [3, 3, 3], [4, 4, 4]]threshold = 14return = 2

Every 2 x 2 sub-matrix has sum at most 14, while the 3 x 3 matrix has sum 27.

3 x 3 sub-matrix

222
333
444
Sum = 27

Example 4

matrix = [[2, 2, 2], [3, 3, 3], [4, 4, 4]]threshold = 27return = 3

The complete 3 x 3 matrix has sum 27, so the entire matrix satisfies the condition.

Constraints

  • 1 <= n <= 750
  • 1 <= threshold <= 10^9
  • 1 <= matrix[i][j] <= 10^7
  • The sum of the entire grid is at most 10^9.

More IMC problems

drafts saved locally
public int maxSize(int[][] matrix, int threshold) {
  // write your code here
}
matrix[[2, 2, 2], [3, 3, 3], [4, 4, 4]]
threshold3
expected0
checking account