🔲 Beginner-Friendly Guide 'Maximum Side Length of a Square' – LeetCode 1292 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

You’re given

• A 2‑D matrix of integers called mat.
• An integer called threshold.

Your goal

Return the maximum side length of a square sub‑matrix whose elements sum to a value ≤ threshold.
If no such square exists, return 0.

Walkthrough: Understanding the Examples

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 = 4

• Side length 1 → any single 1 works.
• Side length 2 → the top‑left square [[1,1],[1,1]] has sum 4 → valid.
• Side length 3 → the smallest 3×3 square already exceeds 4.

Output

2

Example 2

Input

mat = [
  [2,2,2,2,2],
  [2,2,2,2,2],
  ...
]
threshold = 1

Every element is 2, so even a 1×1 square exceeds the threshold.

Output

0

Intuition

To solve this efficiently we combine two powerful techniques:

1. 2‑D Prefix Sums – Pre‑process the matrix so any square’s sum can be obtained in O(1) time.
2. Binary Search on the answer – The side length is monotonic: if a square of size k works, any smaller size also works. This lets us find the maximum valid k in O(log min(m,n)) time.

1️⃣ 2‑D Prefix Sum

preSum[i][j] stores the sum of the rectangle from the top‑left corner (0,0) to (i‑1, j‑1) (inclusive).

The sum of a square with side length len whose bottom‑right corner is (i, j) is:

sum = preSum[i][j]
      - preSum[i‑len][j]
      - preSum[i][j‑len]
      + preSum[i‑len][j‑len]

All indices are 1‑based in the preSum table, so the formula works in O(1).

2️⃣ Binary Search on Answer

• Low = 0, High = min(rows, cols).
• While low ≤ high:
  • mid = (low + high) // 2.
  • Check if any mid × mid square has sum ≤ threshold using the prefix sums.
  • If found, record mid as a candidate and search larger (low = mid + 1).
  • Otherwise, search smaller (high = mid - 1).

The overall complexity is O(m·n + m·n·log min(m,n)), dominated by the prefix‑sum construction and the binary‑search checks.

Code Blocks

C++ (partial)

class Solution {
public:
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> preSum(m + 1, vector<int>(n + 1, 0));

        // Build 2‑D Prefix Sum
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                preSum[i][j] = mat[i-1][j-1] + preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1];
            }
        }
        // ... (rest of the algorithm)
    }
};

Python (partial)

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        m, n = len(mat), len(mat[0])
        preSum = [[0] * (n + 1) for _ in range(m + 1)]

        # Build 2‑D Prefix Sum
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                preSum[i][j] = (mat[i - 1][j - 1] +
                                preSum[i - 1][j] +
                                preSum[i][j - 1] -
                                preSum[i - 1][j - 1])

        def check(k: int) -> bool:
            if k == 0:
                return True
            for i in range(k, m + 1):
                for j in range(k, n + 1):
                    cur = (preSum[i][j] -
                           preSum[i - k][j] -
                           preSum[i][j - k] +
                           preSum[i - k][j - k])
                    if cur <= threshold:
                        return True
            return False

        # Binary search omitted for brevity

JavaScript (partial)

var maxSideLength = function(mat, threshold) {
    const m = mat.length, n = mat[0].length;
    const preSum = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

    // Build 2‑D Prefix Sum
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            preSum[i][j] = mat[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
        }
    }

    const canFit = (k) => {
        if (k === 0) return true;
        for (let i = k; i <= m; ++i) {
            for (let j = k; j <= n; ++j) {
                const cur = preSum[i][j] - preSum[i - k][j] - preSum[i][j - k] + preSum[i - k][j - k];
                if (cur <= threshold) return true;
            }
        }
        return false;
    };

    // Binary search omitted for brevity
};

Cleaned JavaScript Implementation

for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
        preSum[i][j] = mat[i - 1][j - 1] + preSum[i - 1][j] + 
                       preSum[i][j - 1] - preSum[i - 1][j - 1];
    }
}

let low = 0;
let high = Math.min(m, n);
let ans = 0;

while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2);
    if (mid === 0) {
        low = mid + 1;
        continue;
    }

    let found = false;
    for (let i = mid; i <= m; i++) {
        for (let j = mid; j <= n; j++) {
            let currentSum = preSum[i][j] - preSum[i - mid][j] -
                             preSum[i][j - mid] + preSum[i - mid][j - mid];
            if (currentSum <= threshold) {
                found = true;
                break;
            }
        }
        if (found) break;
    }

    if (found) {
        ans = mid;
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}
return ans;

Key Takeaways

• 2D Prefix Sums: This technique reduces region‑sum queries from O(k²) to O(1) after preprocessing. It is a must‑know for grid‑based problems.
• Binary Search on Results: When asked to find a “maximum” or “minimum” value that satisfies a condition, consider if the search space is sorted and apply binary search.
• Inclusion‑Exclusion Principle: The formula for the prefix sum and the area sum is a direct application of this principle, ensuring we don’t double‑count overlapping areas.

Final Thoughts

This problem is a fantastic example of how combining two relatively simple concepts can lead to a highly optimized solution. In the real world, these types of spatial queries are used in Computer Vision for object detection and in Geographic Information Systems (GIS) to analyze data density within specific map regions. Mastering the 2D prefix sum will give you a significant advantage in any interview involving matrix manipulation.