Here, it's easier to think about the 1D first (I've also added the algorithm for in the code). The problem there would be finding the longest line, sum of which is less than or equal to the threshold. We can begin by assuming that the longest length len is 0. When looping through the array, if we come across a line that is longer than the len, then we should update len. Now, if len becomes 5, that means that we don't need to check lines of length < 5. At any index, if the sum of the elements up to the index minus the sum of the elements up to index-len-1 is less than or equal to the threshold, that means that len has to be incremented. So, we use prefix sums to find the solution to this problem.
The same can be done with matrices. At each entry i-j, the sum of the square of side length len+1 can be calculated with prefix matrix sums. The sum of such squares are equal to:
sum[i][j] - sum[i - len][j] - sum[i][j - len] + sum[i - len][j - len]
To visualize:
The square sum for the green square on the bottom right is equal to the matrix sum at that point minus the matrix the sum of the excluded rows minus the matrix sum of the sxcluded columns + the double-subtracted intersection of the two.
Problem: https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/
Algorithm:
Here, it's easier to think about the 1D first (I've also added the algorithm for in the code). The problem there would be finding the longest line, sum of which is less than or equal to the threshold. We can begin by assuming that the longest length
lenis 0. When looping through the array, if we come across a line that is longer than thelen, then we should updatelen. Now, iflenbecomes 5, that means that we don't need to check lines oflength < 5. At any index, if the sum of the elements up to theindexminus the sum of the elements up toindex-len-1is less than or equal to the threshold, that means thatlenhas to be incremented. So, we use prefix sums to find the solution to this problem.The same can be done with matrices. At each entry i-j, the sum of the square of side length
The square sum for the green square on the bottom right is equal to the matrix sum at that point minus the matrix the sum of the excluded rows minus the matrix sum of the sxcluded columns + the double-subtracted intersection of the two.
len+1can be calculated with prefix matrix sums. The sum of such squares are equal to:sum[i][j] - sum[i - len][j] - sum[i][j - len] + sum[i - len][j - len]To visualize: