Finding the perfect sub-section of a data grid is a classic challenge in computer science. In this problem, we explore how to efficiently calculate the sums of various squares within a matrix to find the largest one that stays under a specific limit.
Problem Summary
You're given:
- A 2D matrix of integers called
mat. - An integer called
threshold.
Your goal:
- Return the maximum side length of a square sub-matrix whose elements sum up to a value less than or equal to the
threshold. If no such square exists, return 0.
Walkthrough: Understanding the Examples
To better understand the logic, let's look at the examples provided in the problem.
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
- If we pick a side length of 1: Any single
1in the matrix is . - If we pick a side length of 2: The top-left square is
[[1,1], [1,1]]. The sum is . Since , this is valid. - If we pick a side length of 3: The smallest square sum exceeds 4.
- Output: 2.
Example 2:
Input: mat = [[2,2,2,2,2], [2,2,2,2,2], ...], threshold = 1
- Every single element in the matrix is 2.
- Even the smallest possible square (side length 1) has a sum of 2, which is greater than the threshold of 1.
- Output: 0.
Intuition
To solve this problem efficiently, we combine two powerful techniques: 2D Prefix Sums and Binary Search.
1. 2D Prefix Sum
Calculating the sum of a square by iterating through every element repeatedly is too slow. Instead, we pre-process the matrix into a preSum table. Each entry preSum[i][j] stores the sum of all numbers in the rectangle from the top-left corner to .
With this table, we can calculate the sum of any square with side length in constant time using the formula:
2. Binary Search on Answer
The possible side lengths range from 0 to the minimum of the matrix dimensions. Since if a square of side length works, any smaller square will also work (assuming non-negative numbers), the property is monotonic. This allows us to use Binary Search to find the maximum valid side length efficiently.
Code Blocks
C++
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 2D 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];
}
}
int low = 0, high = min(m, n), ans = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (mid == 0) {
low = mid + 1;
continue;
}
bool found = false;
for (int i = mid; i <= m; i++) {
for (int j = mid; j <= n; j++) {
int 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;
}
};
Python
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 2D 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(mid):
if mid == 0: return True
for i in range(mid, m + 1):
for j in range(mid, n + 1):
current_sum = (preSum[i][j] - preSum[i - mid][j] -
preSum[i][j - mid] + preSum[i - mid][j - mid])
if current_sum <= threshold:
return True
return False
low, high = 0, min(m, n)
ans = 0
while low <= high:
mid = (low + high) // 2
if check(mid):
ans = mid
low = mid + 1
else:
high = mid - 1
return ans
JavaScript
/**
* @param {number[][]} mat
* @param {number} threshold
* @return {number}
*/
var maxSideLength = function(mat, threshold) {
const m = mat.length;
const n = mat[0].length;
const preSum = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
// Build 2D 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];
}
}
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 to . 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.
- 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.
Top comments (0)