# Maximum Side Length of a Square with Sum Less than or Equal to Threshold
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold)
Canonical: https://scaleengineer.com/dsa/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Matrix
**Companies:** [IMC](https://scaleengineer.com/companies/imc)
---
## 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 to_ `threshold` _or return_ `0` _if there is no such square_.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/image0.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:**

**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] <= 104`
* `0 <= threshold <= 105`

# Approaches
## Iteration over Side Lengths with Prefix Sums
This approach improves upon a naive brute-force method by first pre-calculating a 2D prefix sum array (also known as a summed-area table). This allows the sum of any rectangular submatrix to be calculated in constant time. The main algorithm then iterates through all possible square side lengths, from largest to smallest. For each side length, it checks every possible square of that size. The first one found that satisfies the sum condition corresponds to the maximum side length.
**Time:** O(m * n * min(m, n)). The prefix sum calculation is `O(m*n)`. The main part involves three nested loops for side length `k`, row `r`, and column `c`, resulting in a cubic time complexity relative to the matrix dimensions. · **Space:** O(m * n) to store the 2D prefix sum array.
**Pros:** Conceptually simpler to understand and implement than a binary search approach.; Significantly more efficient than a naive brute-force solution that doesn't use prefix sums.
**Cons:** The time complexity of `O(m * n * min(m, n))` can be too slow if the matrix dimensions are very large, although it may pass for the given constraints.; It performs many checks that could be avoided with a more targeted search strategy like binary search.
### Explanation
The core of this method is the optimization of the sum calculation. Instead of summing up `k*k` elements for every square, we pre-process the matrix in `O(m*n)` time to build a `prefix` sum array. `prefix[i+1][j+1]` stores the sum of all elements in the rectangle from `mat[0][0]` to `mat[i][j]`. 

With the `prefix` array, the sum of a square with top-left corner `(r, c)` and side length `k` can be found in `O(1)` using an inclusion-exclusion principle. The algorithm then searches for the answer by checking side lengths in a linear scan, from `min(m, n)` down to 1. The first side length `k` for which a valid square is found is guaranteed to be the maximum, so we can return it immediately. If the scan completes, no valid square exists, and we return 0.

```java
class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] prefix = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = mat[i - 1][j - 1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
            }
        }

        for (int k = Math.min(m, n); k >= 1; k--) {
            for (int r = 0; r <= m - k; r++) {
                for (int c = 0; c <= n - k; c++) {
                    // In the prefix sum array, the indices are 1-based.
                    // A square from (r, c) to (r+k-1, c+k-1) in mat corresponds to
                    // the rectangle between (r, c) and (r+k, c+k) in the prefix sum grid.
                    int sum = prefix[r + k][c + k] - prefix[r][c + k] - prefix[r + k][c] + prefix[r][c];
                    if (sum <= threshold) {
                        return k; // Found the largest possible k
                    }
                }
            }
        }
        
        return 0; // No square found
    }
}
```
### Algorithm
*   **Preprocessing: Prefix Sums**
    1.  Create a 2D prefix sum array, `prefix`, of size `(m+1) x (n+1)` to store cumulative sums.
    2.  Iterate through the input matrix `mat` to populate the `prefix` array. The sum of the rectangle from `(0,0)` to `(i-1,j-1)` is calculated as: `prefix[i][j] = mat[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]`.
*   **Main Logic: Iteration**
    1.  Iterate through all possible side lengths `k` in descending order, from `min(m, n)` down to 1.
    2.  For each `k`, iterate through all possible top-left corners `(r, c)` of a `k x k` square.
    3.  Calculate the sum of the current square in `O(1)` time using the `prefix` array: `sum = prefix[r+k][c+k] - prefix[r][c+k] - prefix[r+k][c] + prefix[r][c]`.
    4.  If `sum <= threshold`, we have found a valid square. Since we are iterating `k` from largest to smallest, this `k` must be the maximum possible side length. Return `k` immediately.
    5.  If the loops complete without finding any valid square, it means no such square exists. Return 0.

## Binary Search on Side Length with Prefix Sums
This approach optimizes the search for the maximum side length by using binary search. The key observation is that the problem has a monotonic property: if a square of side length `k` with a sum less than or equal to the threshold exists, then a valid square of any side length smaller than `k` must also exist (since all matrix elements are non-negative). This allows us to efficiently search for the maximum valid side length in the range `[0, min(m, n)]`.
**Time:** O(m * n * log(min(m, n))). The `log(min(m, n))` factor comes from the binary search. For each of the `log` steps, we perform a check that takes `O(m*n)` time. The initial prefix sum calculation takes `O(m*n)`. · **Space:** O(m * n) to store the 2D prefix sum array.
**Pros:** Highly efficient, with a time complexity that is significantly better than a linear scan.; It is the optimal approach for the given constraints.; Leverages a standard and powerful algorithmic pattern (binary search on the answer).
**Cons:** Slightly more complex to implement due to the binary search logic and the need for a helper function.
### Explanation
The foundation of this method is to transform the problem from finding a maximum value to a series of decision problems. Instead of asking "What is the max length?", we ask "Does a square of length `k` exist?". This yes/no question can be answered efficiently.

First, we pre-compute the 2D prefix sum array in `O(m*n)` time, which allows for `O(1)` sum queries for any submatrix.

Then, we perform a binary search on the possible side lengths `k`. For each `mid` value in our binary search, we have a helper function, `hasValidSquare(mid)`, which determines if there's any square of size `mid x mid` with a sum `<= threshold`. This check takes `O(m*n)` time.

If `hasValidSquare(mid)` is true, we know `mid` is a potential answer, and we try to find an even larger one by searching in the upper half (`low = mid + 1`). If it's false, `mid` is too large, and we must search for a smaller side length in the lower half (`high = mid - 1`). The largest `mid` for which the check was successful is stored and eventually returned as the answer.

```java
class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] prefix = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = mat[i - 1][j - 1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
            }
        }

        int low = 0, high = Math.min(m, n), ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) {
                low = mid + 1;
                continue;
            }
            if (hasValidSquare(mid, m, n, prefix, threshold)) {
                ans = mid; // mid is a possible answer, try for a larger one
                low = mid + 1;
            } else {
                high = mid - 1; // mid is too large, try a smaller one
            }
        }
        return ans;
    }

    private boolean hasValidSquare(int k, int m, int n, int[][] prefix, int threshold) {
        for (int r = 0; r <= m - k; r++) {
            for (int c = 0; c <= n - k; c++) {
                int sum = prefix[r + k][c + k] - prefix[r][c + k] - prefix[r + k][c] + prefix[r][c];
                if (sum <= threshold) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
*   **Preprocessing: Prefix Sums**
    1.  As in the previous approach, create and populate a `(m+1) x (n+1)` 2D prefix sum array in `O(m*n)` time.
*   **Helper Function: `hasValidSquare(k)`**
    1.  Create a function that takes a side length `k` and checks if any `k x k` square has a sum less than or equal to `threshold`.
    2.  This function iterates through all possible `k x k` squares, calculates their sum in `O(1)` using the prefix sum array, and returns `true` if a valid one is found. Otherwise, it returns `false` after checking all possibilities. This check takes `O(m*n)` time.
*   **Binary Search**
    1.  Initialize search boundaries `low = 0`, `high = min(m, n)`, and a result variable `ans = 0`.
    2.  While `low <= high`:
        a.  Calculate the middle side length `mid = low + (high - low) / 2`.
        b.  Call `hasValidSquare(mid)`.
        c.  If it returns `true`, `mid` is a possible answer. We try for a larger square by setting `ans = mid` and `low = mid + 1`.
        d.  If it returns `false`, `mid` is too large. We search in the lower half by setting `high = mid - 1`.
    3.  Return `ans`.

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int threshold;
private
  int[][] s;
public
  int maxSideLength(int[][] mat, int threshold) {
    m = mat.length;
    n = mat[0].length;
    this.threshold = threshold;
    s = new int[m + 1][n + 1];
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        s[i][j] =
            s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
      }
    }
    int l = 0, r = Math.min(m, n);
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
private
  boolean check(int k) {
    for (int i = 0; i < m - k + 1; ++i) {
      for (int j = 0; j < n - k + 1; ++j) {
        if (s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j] <=
            threshold) {
          return true;
        }
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxSideLength(vector<vector<int>> &mat, int threshold) {
    int m = mat.size(), n = mat[0].size();
    int s[m + 1][n + 1];
    memset(s, 0, sizeof(s));
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        s[i][j] =
            s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
      }
    }
    auto check = [&](int k) {
      for (int i = 0; i < m - k + 1; ++i) {
        for (int j = 0; j < n - k + 1; ++j) {
          if (s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j] <=
              threshold) {
            return true;
          }
        }
      }
      return false;
    };
    int l = 0, r = min(m, n);
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
};

```

### Python

```python
class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int: def check(k: int) -> bool: for i in range(m - k + 1): for j in range(n - k + 1): v = s[i + k][j + k] - s[i][j + k] - s[i + k][j] + s[i][j] if v <= threshold: return True return False m, n = len(mat), len(mat[0]) s = [[0] * (n + 1) for _ in range(m + 1)] for i, row in enumerate(mat, 1): for j, x in enumerate(row, 1): s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x l, r = 0, min(m, n) while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return l

```