Problem Brief

Sub-matrix Sums

FULLTIMEOA

Given an n x n matrix of integers and an integer value, threshold, determine the maximum size of a square sub-matrix such that for all square sub-matrices of that size, the sum of all elements in each square sub-matrix is less than or equal to the value threshold.

Function Description

Complete the function maxSubmatrixSumSize in the editor.

maxSubmatrixSumSize has the following parameters:

1. int[][] matrix: a 2D array of integers
2. int threshold: the maximum sum of all square sub-matrices of a size must be less than or equal to this integer value

Returns

int: the maximum size of the square sub-matrix

1Example 1

Input

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

Output

Explanation

The maximum 1x1 matrix has a sum of 4. If threshold < 4 there is no size square sub-matrix that satisfies the condition. The answer is 0.

1x1 sub-matrices Maximum sub-matrix sum = 4

2Example 2

Input

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

Output

Explanation

The maximum 2x2 matrix has a sum of 14. If 4 ≤ threshold < 14, the maximum size of the square sub-matrix is 1.

2x2 sub-matrices Maximum sub-matrix sum = 14 (3 + 3 + 4 + 4 = 14)

3Example 3

Input

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

Output

Explanation

The maximum 3x3 matrix has a sum of 27. If 14 ≤ threshold < 27, the maximum size of the square sub-matrix is 2.

3x3 sub-matrices Maximum sub-matrix sum = 27 (2 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 = 27)