FastPrep
Problem · Matrix

Sub-matrix Sums

Learn this problem
● MediumIMCOA

Problem statement

Given an n x n matrix of positive integers and an integer k, return the largest size s such that every s x s sub-matrix has a sum less than or equal to k.

Return 0 when no positive square size satisfies the condition.

Function

maxSubSquareMatrixSumLessThanK(matrix: int[][], k: int) → int

Complete maxSubSquareMatrixSumLessThanK with the following parameters:

  • int[][] matrix: an n x n matrix
  • int k: the maximum allowed sum for every square of the selected size

Examples

Example 1

matrix = [[2, 2, 2], [3, 3, 3], [4, 4, 4]]k = 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]]k = 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]]k = 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]]k = 27return = 3

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

Constraints

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

More IMC problems

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