Maximum Side Length of a Square with Sum Less than or Equal to Threshold - Problem

Given a m x n matrix mat and an integer threshold, return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

A square is defined as a submatrix where all sides have equal length. The sum of a square is the sum of all elements within that submatrix.

Input & Output

Example 1 — Basic Case

$ 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

› Output: 2

💡 Note: The maximum side-length of a square with sum ≤ 4 is 2. The 2×2 square at position (0,0) has sum = 1+1+1+1 = 4.

Example 2 — Larger Threshold

$ Input: mat = [[2,2,2,2,5,5],[2,2,2,2,5,5],[2,2,2,2,5,5],[2,2,2,2,5,5]], threshold = 18

› Output: 2

💡 Note: A 2×2 square of all 2's has sum = 8 ≤ 18. A 3×3 square would have sum ≥ 18, but we need strictly ≤ threshold.

Example 3 — No Valid Square

$ Input: mat = [[1,1,1,1],[1,1,1,1],[1,1,1,1]], threshold = 0

› Output: 0

💡 Note: Even the smallest 1×1 square has sum = 1 > 0, so no valid square exists.

Constraints

1 ≤ m, n ≤ 300
0 ≤ mat[i][j] ≤ 10⁴
0 ≤ threshold ≤ 10⁵

Visualization

Tap to expand

Asked in

G Google 35 a Amazon 28 f Facebook 22

The key insight is using 2D prefix sums to calculate rectangle sums in O(1) time. The optimal approach combines binary search on the answer space with prefix sum validation, achieving O(mn log(min(m,n))) time complexity.

Common Approaches

✓ Binary Search on Answer

⏱️ Time: O(mn log(min(m,n))) Space: O(mn)

Since we want the maximum valid square size, we can binary search on the answer. For each candidate size, we check if there exists at least one square of that size with sum ≤ threshold using prefix sums.

Brute Force

⏱️ Time: O(m²n²k) Space: O(1)

For each possible square size and position, calculate the sum by iterating through all elements in the square. Keep track of the maximum valid size found.

Prefix Sum Optimization

⏱️ Time: O(mn + m²n²) Space: O(mn)

Build a 2D prefix sum array where each cell contains the sum of all elements from top-left corner to that position. This allows us to calculate any rectangle sum in constant time using the inclusion-exclusion principle.

Binary Search on Answer — Algorithm Steps

Build 2D prefix sum array
Binary search on square size from 0 to min(m,n)
For each size, check if any square is valid
Return maximum valid size found

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Space

Size range [0, min(m,n)]

Test Middle

Check if size is achievable

Narrow Range

Eliminate half the search space

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int** prefix;
int m, n;

int min(int a, int b) {
    return a < b ? a : b;
}

bool canFindSquare(int size, int threshold) {
    for (int i = 0; i <= m - size; i++) {
        for (int j = 0; j <= n - size; j++) {
            int x1 = i, y1 = j;
            int x2 = i + size - 1, y2 = j + size - 1;
            int squareSum = prefix[x2+1][y2+1] - prefix[x1][y2+1] - prefix[x2+1][y1] + prefix[x1][y1];
            if (squareSum <= threshold) {
                return true;
            }
        }
    }
    return false;
}

int solution(int** mat, int rows, int cols, int threshold) {
    m = rows;
    n = cols;
    
    // Allocate prefix sum array
    prefix = (int**)malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        prefix[i] = (int*)calloc(n + 1, sizeof(int));
    }
    
    // Build prefix sum array
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            prefix[i][j] = mat[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
        }
    }
    
    // Binary search on answer
    int left = 0, right = min(m, n);
    int result = 0;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (canFindSquare(mid, threshold)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    // Free memory
    for (int i = 0; i <= m; i++) {
        free(prefix[i]);
    }
    free(prefix);
    
    return result;
}

void parseMatrix(char* line, int*** mat, int* rows, int* cols) {
    *rows = 0;
    *cols = 0;
    
    // Count rows by counting inner '['
    char* p = line;
    while (*p) {
        if (*p == '[' && *(p+1) != '[') {
            (*rows)++;
        }
        p++;
    }
    
    if (*rows == 0) return;
    
    // Count columns by parsing first row
    p = line;
    // Find first inner '['
    while (*p && !(*p == '[' && *(p+1) != '[')) p++;
    if (!*p) return;
    p++; // skip '['
    
    // Count numbers in first row
    while (*p && *p != ']') {
        if (*p >= '0' && *p <= '9') {
            (*cols)++;
            // Skip the entire number
            while (*p && *p >= '0' && *p <= '9') p++;
        } else {
            p++;
        }
    }
    
    if (*cols == 0) return;
    
    // Allocate matrix
    *mat = (int**)malloc(*rows * sizeof(int*));
    for (int i = 0; i < *rows; i++) {
        (*mat)[i] = (int*)malloc(*cols * sizeof(int));
    }
    
    // Parse matrix values
    p = line;
    int row = 0, col = 0;
    
    while (*p && row < *rows) {
        if (*p == '[' && *(p+1) != '[') {
            // Start of a row
            col = 0;
            p++;
        } else if (*p == ']' && row < *rows) {
            // End of current row
            row++;
            p++;
        } else if (*p >= '0' && *p <= '9') {
            // Parse number
            if (row < *rows && col < *cols) {
                char* endp;
                (*mat)[row][col] = (int)strtol(p, &endp, 10);
                col++;
                p = endp;
            } else {
                // Skip this number
                while (*p && *p >= '0' && *p <= '9') p++;
            }
        } else {
            p++;
        }
    }
}

int main() {
    char line[10000];
    if (!fgets(line, sizeof(line), stdin)) {
        return 1;
    }
    
    // Remove newline
    line[strcspn(line, "\n")] = 0;
    
    int** mat;
    int rows = 0, cols = 0;
    parseMatrix(line, &mat, &rows, &cols);
    
    if (rows == 0 || cols == 0) {
        return 1;
    }
    
    int threshold;
    scanf("%d", &threshold);
    
    int result = solution(mat, rows, cols, threshold);
    printf("%d\n", result);
    
    for (int i = 0; i < rows; i++) {
        free(mat[i]);
    }
    free(mat);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn log(min(m,n)))

O(mn) to build prefix + O(log(min(m,n))) binary search iterations × O(mn) to check all positions

⚠ Quadratic Growth

Space Complexity

O(mn)

Extra 2D array to store prefix sums

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Maximum Side Length of a Square with Sum Less than or Equal to Threshold - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler