1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

At first glance, Maximum Side Length of a Square with Sum Less than or Equal to Threshold looks like a routine matrix problem. But in FAANG and similar top-tier interviews, it is really a test of whether you can recognize hidden inefficiencies in brute-force grid traversal.

Problem statement

You’re given a 2D grid of non-negative integers, mat and a number called threshold. Your task is to find the largest possible square (same number of rows and columns) you can take from the grid such that the sum of all values inside that square is less than or equal to threshold. Return the square’s side length, or 0 if no valid square exists.

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 300
• 0 <= mat[i][j] <= 10⁴
• 0 <= threshold <= 10⁵

Examples

Why checking every square is inefficient

A direct approach would try every top-left corner and every possible side length, then compute each square’s sum by walking all of its cells. The problem is that this repeats an enormous amount of work: neighboring squares overlap heavily, but the naive method still recalculates almost the same totals from scratch each time. On a grid as large as 300×300, the number of candidate squares grows quickly, and once you factor in the cost of re-summing each interior, the runtime becomes unrealistic for interview constraints.

Optimized approach using Prefix sum + Binary search

If we first build a 2D prefix sum array, we can compute the sum of any sub-rectangle (including any square) in constant time. Instead of adding up L×L cells every time we test a square, we use four prefix values to “include–exclude” the area we want.

This eliminates the repeated work found in brute force: each square’s sum becomes an O(1) query, so checking a square no longer depends on its size.

After that, the remaining problem is to find the largest side length that can work. Because all numbers in the grid are non-negative, feasibility has a monotonic behavior: if there exists any square of side length L with sum ≤ threshold, then every smaller length is also feasible (smaller squares contain fewer or equal total value). This monotonic “works / doesn’t work” pattern lets us apply binary search over possible side lengths from 0 to min(m, n).

For each candidate side length L chosen by binary search, we perform a feasibility check: we scan all possible top-left positions (r, c) where an L×L square fits in the matrix, and for each position we compute its square sum using the prefix sums in O(1). If we find even one square whose sum is ≤ threshold, then L is feasible and we try a larger L; otherwise we reduce L. In the end, binary search converges to the maximum side length that satisfies the condition efficiently.

Solution steps

1. Let m and n be the number of rows and columns in mat.
2. Build a (m + 1) × (n + 1) prefix-sum array ps (with an extra top row and left column of zeros) where ps[i][j] stores the sum of the submatrix from (0, 0) to (i - 1, j - 1).
3. Define a helper square_sum(r, c, L) that returns the sum of the L×L square starting at (r, c) using: ps[r+L][c+L] - ps[r][c+L] - ps[r+L][c] + ps[r][c].
4. Define feasible(L):
   1. If L == 0, return True.
   2. For every top-left position (r, c) where an L×L square fits (0 ≤ r ≤ m-L, 0 ≤ c ≤ n-L), compute square_sum(r, c, L).
   3. If any square sum ≤ threshold, return True; otherwise return False.
5. Binary search the answer L between 0 and min(m, n):
   1. Compute mid = (lo + hi + 1) // 2.
   2. If feasible(mid) is True, set lo = mid (try bigger squares).
   3. Else set hi = mid - 1 (try smaller squares).
6. Return lo as the maximum side length that satisfies the threshold.

Let’s look at the following illustration to get a better understanding of the solution.

1 / 10

Solution implementation

def maxSideLength(mat, threshold):
    m, n = len(mat), len(mat[0])

    # Build 2D prefix sums with 1-based padding.
    ps = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        row_sum = 0
        for j in range(1, n + 1):
            row_sum += mat[i - 1][j - 1]
            ps[i][j] = ps[i - 1][j] + row_sum

    def square_sum(r, c, L):
        """Sum of LxL square with top-left at (r, c) in 0-based mat indices."""
        r2, c2 = r + L, c + L
        return ps[r2][c2] - ps[r][c2] - ps[r2][c] + ps[r][c]

    def feasible(L):
        """Return True if any LxL square has sum <= threshold."""
        if L == 0:
            return True
        limit_r = m - L
        limit_c = n - L
        for r in range(limit_r + 1):
            for c in range(limit_c + 1):
                if square_sum(r, c, L) <= threshold:
                    return True
        return False

    lo, hi = 0, min(m, n)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if feasible(mid):
            lo = mid
        else:
            hi = mid - 1

    return lo
    
def main():
    
    mat3d = [
        [[1, 1, 3, 2, 4, 3, 2],
         [1, 1, 3, 2, 4, 3, 2],
         [1, 1, 3, 2, 4, 3, 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, 2]],

        [[1, 1, 1],
         [1, 1, 1],
         [1, 1, 1]],

        [[5, 1, 3],
         [2, 4, 6],
         [1, 1, 1]],

        [[7]],
    ]

    thresholds = [4, 1, 9, 10, 7]

    for i in range(len(mat3d)):
        print("\tMatrix:", mat3d[i])
        print("\tThreshold:", thresholds[i])
        ans = maxSideLength(mat3d[i], thresholds[i])
        print("\n\tMax side length =", ans)
        print("-"*75)

if __name__ == "__main__":
    main()

Time complexity

Building the 2D prefix sum takes O(m * n) time because each cell is processed once. The binary search performs O(log(min(m, n))) checks, and each feasibility check scans all possible LxL top-left positions, which is O(m * n) in the worst case. Overall, the runtime is O(m * n * log(min(m, n))).

Space complexity

The prefix sum array uses O(m * n) extra space (technically (m+1) * (n+1)), which dominates the memory usage. Other variables use only constant extra space, so worst-case space is O(m * n).

Edge cases

• Threshold too small to fit any cell
  Example: mat = [[2]], threshold = 1
  Why it works: the feasibility check for L=1 fails, so binary search returns 0.
• Threshold is 0 with zeros present
  Example: mat = [[0, 1], [0, 0]], threshold = 0
  Why it works: prefix sums correctly compute zero-sum squares; feasibility finds the largest all-zero square.
• Single row or single column matrix
  Example: mat = [[1, 1, 1]], threshold = 2
  Why it works: the maximum square side cannot exceed 1, and the search bounds handle that (min(m, n)).
• Maximum possible square fits
  Example: mat = [[1,1],[1,1]], threshold = 4
  Why it works: feasibility will succeed for L=2, and binary search returns the full size.

Common pitfalls

• Off-by-one errors in prefix sum indexing: Using 1-based padding avoids negative indices and makes rectangle queries consistent.
• Incorrect square sum formula: The inclusion-exclusion must subtract the top and left rectangles and add back the overlap.
• Binary search mid calculation: Using the upper-mid (lo + hi + 1) // 2 prevents infinite loops when moving lo up.
• Not handling L=0: Treating L=0 as feasible keeps the binary search logic clean and guarantees a valid baseline.
• Scanning bounds wrong: The last valid top-left is (m - L, n - L); missing the +1 drops candidates.