### Problem Statement

Given a

`m x n`

matrix `mat`

and an integer `threshold`

. Return the maximum side-length of a square with a sum less than or equal to `threshold`

or return **0**if there is no such square.**Example 1:**

Input:mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4Output:2Explanation:The maximum side length of square with sum less than 4 is 2 as shown.

**Example 2:**

Input:mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1Output:0

**Example 3:**

Input:mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6Output:3

**Example 4:**

Input:mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184Output:2

**Constraints:**

`1 <= m, n <= 300`

`m == mat.length`

`n == mat[i].length`

`0 <= mat[i][j] <= 10000`

`0 <= threshold <= 10^5`

### Video Tutorial

You can find the detailed video tutorial here### Thought Process

There is an absolute brute force way is to calculate the sum of each square in every iteration. There are previous similar problems that we can have a prefix sum matrix, similar to the rolling sum idea on one dimensional array.A prefix sum matrix is a matrix that for each cell[i, j] represents the sum in original matrix from matrix[0, 0] to matrix [i, j] (inclusive)

The advantage is later we can get any rectangle sum simply performing below

sum from [i, j] to [i + len][j + len] = prefixSum[i + len][j + len] - prefixSum[i - 1][j + len] - prefixSum[i + len][j - 1] + prefixSum[i - 1][j - 1]Two more optimizations we can do

- We can apply binary search instead of a linear one to find the max length
- We can also keep a record of the sum while building up the prefix sum matrix. The reason this works is if it has a square say 3x3 that meets the requirement, then it would definitely have a square 2x2 meet the requirement. So we can start from 1x1, 2x2 till we reach the max. Pretty smart! Kudos to @drunkpiano

- Reference is here: Leetcode discussion solution with binary search and smart solution

### Solutions

#### Prefix sum implementation

Time Complexity: O(M*N*min(M,N)) where M is row N is col, essentially O(N^3)Space Complexity: O(M*N) since we need

References

Thanks. It was very helpful. Your diagrams really helped in understanding. I've a little doubt. In that Brute Force Solution, why are returning len+1 instead of len?

ReplyDelete> Thank you for your reply and that's a good catch. You can think of Len as the delta distance, as a matter of fact, I would probably rename length as delta, and star the for loop with

for (int len = Math.min(row, col) ; len >= 1; len--) -> for (int len = Math.min(row, col) - 1; len >= 1; len--)