LeetCode 1292 Solution: Maximum Side Length of a Square (Prefix Sum + Binary Search)

🔍 Problem Overview

You are given an m x n matrix mat of non-negative integers and an integer threshold.

Your task is to find the maximum possible side length of a square submatrix such that the sum of all its elements is less than or equal to threshold.

Example

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

---

💡 Key Insight

A brute-force approach that checks every square and sums its elements would be too slow
→ O(n⁴) in the worst case.

To solve this efficiently, we combine:

1. 2D Prefix Sum (for fast submatrix sum queries)
2. Binary Search (to find the maximum valid square size)

---

🧮 Step 1: Build a 2D Prefix Sum Matrix

The prefix sum matrix allows us to compute the sum of any submatrix in O(1) time.

Definition

prefix[i][j] = sum of all elements from (0,0) to (i-1, j-1)

Formula

prefix[i][j] =
    mat[i-1][j-1]
  + prefix[i-1][j]
  + prefix[i][j-1]
  - prefix[i-1][j-1]

---

📐 Step 2: Compute Any Square Sum in O(1)

For a square of side length k with top-left corner at (r, c):

sum =
  prefix[r+k][c+k]
- prefix[r][c+k]
- prefix[r+k][c]
+ prefix[r][c]

---

🔎 Step 3: Binary Search on Side Length

The maximum possible square side length is min(m, n).

Binary Search Logic

• low = 0, high = min(m, n)
• For each mid:
  • Check if any square of side mid has sum ≤ threshold
  • If yes → try bigger (low = mid)
  • If no → try smaller (high = mid - 1)

---

✅ Final Python Solution

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

        # Build prefix sum matrix
        prefix = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                prefix[i][j] = (
                    mat[i - 1][j - 1]
                    + prefix[i - 1][j]
                    + prefix[i][j - 1]
                    - prefix[i - 1][j - 1]
                )

        # Helper function to check if square of size k exists
        def exists(k):
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    total = (
                        prefix[i + k][j + k]
                        - prefix[i][j + k]
                        - prefix[i + k][j]
                        + prefix[i][j]
                    )
                    if total <= threshold:
                        return True
            return False

        # Binary search on side length
        low, high = 0, min(m, n)
        while low < high:
            mid = (low + high + 1) // 2
            if exists(mid):
                low = mid
            else:
                high = mid - 1

        return low

---

⏱️ Time & Space Complexity

Time Complexity

• Prefix sum: O(m × n)
• Binary search: O(log(min(m,n)))
• Each check: O(m × n)

➡️ Total: O(m × n × log(min(m,n)))

Space Complexity

• Prefix matrix: O(m × n)

---

🧠 Why This Works Well

• Prefix sums eliminate repeated summation
• Binary search avoids checking every possible size
• Clean, scalable, and interview-optimized

---

📌 Takeaway

This problem is a classic example of:

• Preprocessing + Search
• Turning a brute-force problem into an efficient one using math and structure

If you’re preparing for coding interviews, mastering this pattern will help across matrix, DP, and search problems.