How should I practice Sub-matrix Sums?

Start by reading the full statement, solve the visible examples, then compare the pattern against related IMC Trading online assessment problems in FastPrep.

Is Sub-matrix Sums associated with IMC Trading?

FastPrep tags this as a IMC Trading online assessment coding practice problem when the problem catalog has that company and stage context.

Sub-matrix Sums

IMC Trading● MediumNEW GRADOA

Learn

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

All one by one sub-matrices. Bold entries mark selected cells.
Row / column	0	1	2
0	2	2	2
1	3	3	3
2	4	4	4

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

Top-left two by two sub-matrix. Bold entries mark selected cells.
Row / column	0	1	2
0	2	2	2
1	3	3	3
2	4	4	4

Top left

Top-right two by two sub-matrix. Bold entries mark selected cells.
Row / column	0	1	2
0	2	2	2
1	3	3	3
2	4	4	4

Top right

Bottom-left two by two sub-matrix. Bold entries mark selected cells.
Row / column	0	1	2
0	2	2	2
1	3	3	3
2	4	4	4

Bottom left

Bottom-right two by two sub-matrix. Bold entries mark selected cells.
Row / column	0	1	2
0	2	2	2
1	3	3	3
2	4	4	4

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

Complete three by three sub-matrix. Bold entries mark selected cells.
Row / column	0	1	2
0	2	2	2
1	3	3	3
2	4	4	4

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.

Example 5

matrix = [[1,1,1,1],[2,2,2,2],[3,3,3,3],[4,4,4,4]]k = 39return = 3

The maximum square sums for sides 1, 2, 3, 4 are 4, 14, 27, 40. Every 3x3 square is at most 39, but the complete 4x4 sum is 40.

Example 6

matrix = [[4,5],[6,7]]k = 2return = 0

The maximum 1x1 sum is 7, greater than 2, so no positive side length can satisfy the every-square 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.