Problem

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 tothreshold or return0 if there is no such square.

Examples

Example 1

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2019/12/05/e1.png)

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

Example 2

1
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 = 1
Output: 0

Constraints

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 300
  • 0 <= mat[i][j] <= 10^4
  • 0 <= threshold <= 10^5

Solution

Method 1 – Binary Search with 2D Prefix Sum

Intuition

To efficiently check if a square of a given side length has a sum less than or equal to the threshold, we use a 2D prefix sum. We then binary search on the possible side lengths to find the largest valid one.

Approach

  1. Compute a 2D prefix sum for the matrix to allow O(1) sum queries for any submatrix.
  2. Use binary search on the possible side lengths (from 0 to min(m, n)).
  3. For each candidate side length, check all possible top-left corners to see if any square of that size has a sum ≤ threshold.
  4. If such a square exists, try a larger size; otherwise, try smaller.
  5. Return the largest valid side length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> ps(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                ps[i][j] = mat[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];
        int l = 0, r = min(m, n), ans = 0;
        while (l <= r) {
            int k = (l + r) / 2;
            bool found = false;
            for (int i = k; i <= m && !found; ++i)
                for (int j = k; j <= n && !found; ++j)
                    if (ps[i][j] - ps[i-k][j] - ps[i][j-k] + ps[i-k][j-k] <= threshold)
                        found = true;
            if (found) ans = k, l = k + 1;
            else r = k - 1;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func maxSideLength(mat [][]int, threshold int) int {
    m, n := len(mat), len(mat[0])
    ps := make([][]int, m+1)
    for i := range ps {
        ps[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            ps[i][j] = mat[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1]
        }
    }
    l, r, ans := 0, m
    if n < m {
        r = n
    }
    for l <= r {
        k := (l + r) / 2
        found := false
        for i := k; i <= m && !found; i++ {
            for j := k; j <= n && !found; j++ {
                sum := ps[i][j] - ps[i-k][j] - ps[i][j-k] + ps[i-k][j-k]
                if sum <= threshold {
                    found = true
                }
            }
        }
        if found {
            ans = k
            l = k + 1
        } else {
            r = k - 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        int m = mat.length, n = mat[0].length;
        int[][] ps = new int[m+1][n+1];
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                ps[i][j] = mat[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];
        int l = 0, r = Math.min(m, n), ans = 0;
        while (l <= r) {
            int k = (l + r) / 2;
            boolean found = false;
            for (int i = k; i <= m && !found; ++i)
                for (int j = k; j <= n && !found; ++j)
                    if (ps[i][j] - ps[i-k][j] - ps[i][j-k] + ps[i-k][j-k] <= threshold)
                        found = true;
            if (found) { ans = k; l = k + 1; }
            else r = k - 1;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun maxSideLength(mat: Array<IntArray>, threshold: Int): Int {
        val m = mat.size
        val n = mat[0].size
        val ps = Array(m+1) { IntArray(n+1) }
        for (i in 1..m) for (j in 1..n)
            ps[i][j] = mat[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1]
        var l = 0; var r = minOf(m, n); var ans = 0
        while (l <= r) {
            val k = (l + r) / 2
            var found = false
            for (i in k..m) for (j in k..n) {
                if (ps[i][j] - ps[i-k][j] - ps[i][j-k] + ps[i-k][j-k] <= threshold) {
                    found = true; break
                }
            }
            if (found) { ans = k; l = k + 1 }
            else r = k - 1
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def maxSideLength(self, mat: list[list[int]], threshold: int) -> int:
        m, n = len(mat), len(mat[0])
        ps: list[list[int]] = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                ps[i][j] = mat[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1]
        l, r, ans = 0, min(m, n), 0
        while l <= r:
            k = (l + r) // 2
            found = False
            for i in range(k, m+1):
                for j in range(k, n+1):
                    s = ps[i][j] - ps[i-k][j] - ps[i][j-k] + ps[i-k][j-k]
                    if s <= threshold:
                        found = True
                        break
                if found:
                    break
            if found:
                ans = k
                l = k + 1
            else:
                r = k - 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

impl Solution {
    pub fn max_side_length(mat: Vec<Vec<i32>>, threshold: i32) -> i32 {
        let m = mat.len();
        let n = mat[0].len();
        let mut ps = vec![vec![0; n+1]; m+1];
        for i in 1..=m {
            for j in 1..=n {
                ps[i][j] = mat[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];
            }
        }
        let (mut l, mut r, mut ans) = (0, m.min(n), 0);
        while l <= r {
            let k = (l + r) / 2;
            let mut found = false;
            'outer: for i in k..=m {
                for j in k..=n {
                    let s = ps[i][j] - ps[i-k][j] - ps[i][j-k] + ps[i-k][j-k];
                    if s <= threshold {
                        found = true;
                        break 'outer;
                    }
                }
            }
            if found {
                ans = k;
                l = k + 1;
            } else {
                r = k - 1;
            }
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    maxSideLength(mat: number[][], threshold: number): number {
        const m = mat.length, n = mat[0].length;
        const ps: number[][] = Array.from({length: m+1}, () => Array(n+1).fill(0));
        for (let i = 1; i <= m; ++i)
            for (let j = 1; j <= n; ++j)
                ps[i][j] = mat[i-1][j-1] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];
        let l = 0, r = Math.min(m, n), ans = 0;
        while (l <= r) {
            const k = (l + r) >> 1;
            let found = false;
            for (let i = k; i <= m && !found; ++i)
                for (let j = k; j <= n && !found; ++j)
                    if (ps[i][j] - ps[i-k][j] - ps[i][j-k] + ps[i-k][j-k] <= threshold)
                        found = true;
            if (found) { ans = k; l = k + 1; }
            else r = k - 1;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m n log(min(m, n))), where m and n are the matrix dimensions. Each binary search step checks all possible squares.
  • 🧺 Space complexity: O(m n), for the prefix sum matrix.