LeetCode 1292: Maximum Side Length of a Square with Sum Less than or Equal to Threshold Solution

Master LeetCode problem 1292 (Maximum Side Length of a Square with Sum Less than or Equal to Threshold), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

Medium

Array Binary Search Matrix Prefix Sum

Problem Explanation

Explanation

To solve this problem, we can use a prefix sum approach along with binary search to find the maximum side length of a square with a sum less than or equal to the threshold. We iterate over the matrix and calculate the prefix sum for each cell. Then, we iterate over all possible square sizes from 1 to the minimum of m and n. For each square size, we slide a window over the matrix and calculate the sum of the square by using the precomputed prefix sum values. If the sum is less than or equal to the threshold, we update the maximum side length found so far. We use binary search to efficiently find the sum of a square in constant time.

Time Complexity: O(mnlog(min(m,n))) Space Complexity: O(m*n)

Solution Code

class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] prefixSum = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixSum[i][j] = mat[i - 1][j - 1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
            }
        }
        
        int maxSideLength = 0;
        for (int k = 1; k <= Math.min(m, n); k++) {
            for (int i = 1; i <= m - k + 1; i++) {
                for (int j = 1; j <= n - k + 1; j++) {
                    int sum = prefixSum[i+k-1][j+k-1] - prefixSum[i-1][j+k-1] - prefixSum[i+k-1][j-1] + prefixSum[i-1][j-1];
                    if (sum <= threshold) {
                        maxSideLength = Math.max(maxSideLength, k);
                    }
                }
            }
        }
        
        return maxSideLength;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1292 (Maximum Side Length of a Square with Sum Less than or Equal to Threshold)?

This page provides optimized solutions for LeetCode problem 1292 (Maximum Side Length of a Square with Sum Less than or Equal to Threshold) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1292 (Maximum Side Length of a Square with Sum Less than or Equal to Threshold)?

The time complexity for LeetCode 1292 (Maximum Side Length of a Square with Sum Less than or Equal to Threshold) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1292 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1292 in Java, C++, or Python.

Back to LeetCode Solutions