Maximum Side Length Of A Square With Sum Less Than Or Equal To Threshold - Leetcode Solution

Problem Description:

Given a matrix of integers matrix and a threshold, we are to find the maximum side-length of a square with a sum less than or equal to the threshold.

Solution:

First, we can construct a prefix sum matrix prefix. Specifically, prefix[i][j] will represent the sum of the rectangle extending from the top-left corner (0, 0) to the bottom-right corner (i, j) of matrix. Now, given two points (i1, j1) and (i2, j2) such that i1 <= i2 and j1 <= j2, we can calculate the sum of the rectangle with these coordinates as follows:

sum = prefix[i2][j2] - prefix[i1-1][j2] - prefix[i2][j1-1] + prefix[i1-1][j1-1]

This is the classic 2D range sum problem.

Now, we can iterate over all possible squares (whose top-left corner is at position (i, j) for some i and j) and compute their sum using the prefix matrix. If the sum of the square is less than or equal to threshold, then we can check if its sidelength is greater than the current maximum. Finally, we can return the maximum sidelength.

Time Complexity:

The time complexity of this solution is O(m^2 * n^2) where m and n are the dimensions of the matrix. This is because we iterate over all possible squares and for each square, we compute its sum using the prefix matrix.

Space Complexity:

The space complexity of this solution is O(m * n) because we need to construct the prefix matrix.

Here is the Python code implementation of the above solution:

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

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] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1]

max_side = 0
for i in range(m):
    for j in range(n):
        for k in range(max_side, min(m-i, n-j)):
            sum_ = prefix[i+k+1][j+k+1] - prefix[i+k+1][j] - prefix[i][j+k+1] + prefix[i][j]
            if sum_ <= threshold:
                max_side = k+1
            else:
                break

return max_side

Here is the C++ code implementation of the above solution:

int maxSideLength(vector<vector<int>>& matrix, int threshold) { int m = matrix.size(); int n = matrix[0].size();

vector<vector<int>> prefix(m+1, vector<int>(n+1, 0));
for(int i = 1; i <= m; i++){
    for(int j = 1; j <= n; j++){
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1];
    }
}

int max_side = 0;
for(int i = 0; i < m; i++){
    for(int j = 0; j < n; j++){
        for(int k = max_side; k < min(m-i, n-j); k++){
            int sum_ = prefix[i+k+1][j+k+1] - prefix[i+k+1][j] - prefix[i][j+k+1] + prefix[i][j];
            if(sum_ <= threshold){
                max_side = k+1;
            } else {
                break;
            }
        }
    }
}

return max_side;

}

1