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● MediumFULLTIMEOA

Learn

Problem statement

Given an n x n matrix of positive integers and an integer threshold, find the largest size k such that every contiguous k x k sub-matrix has sum at most threshold.

Return the largest valid k. Return 0 if even size 1 is invalid.

Function

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

Examples

Example 1

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

The largest 1 x 1 sum is 4. Since this exceeds the threshold 3, no positive size is valid.

Example 2

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

Every 1 x 1 sum is at most 4, but the largest 2 x 2 sum is 14. Therefore the largest valid size is 1.

Example 3

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

Every 2 x 2 sum is at most 14, while the complete 3 x 3 matrix has sum 27. Therefore the answer is 2.

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 size 3 is valid.

Constraints

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