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

Medium
1376.

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

Maximum Side Length of a Square with Sum Less than or Equal to Threshold is a medium coding problem on arrays, binary search and matrix, asked in Amazon and Google interviews.

You are given an m x n grid mat of non-negative integers and an integer threshold.

A square is any k x k block of adjacent cells (k >= 1). Return the largest side length k such that at least one k x k square has a cell sum of at most threshold. Return 0 if even a single cell exceeds the threshold everywhere.

Example 1

Input
mat = [[2,2,5],[2,2,5],[5,5,5]], threshold = 8
Output
2
Explanation
The top-left 2 x 2 block sums to 8; the whole 3 x 3 grid sums to 33.

Example 2

Input
mat = [[2,3],[4,5]], threshold = 1
Output
0

Example 3

Input
mat = [[1,1,1],[1,1,1],[1,1,1]], threshold = 9
Output
3

Constraints

  • 1 <= m, n <= 300
  • 0 <= mat[i][j] <= 10^4
  • 0 <= threshold <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @param {number} threshold
 * @return {number}
 */
var maxSideLength = function(mat, threshold) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Maximum Side Length of a Square with Sum Less than or Equal to Threshold solution: step-by-step approach, complexity and code in Python, Java, C++ and…

Maximum Side Length of a Square with Sum Less than or Equal to Threshold is a medium coding problem on arrays, binary search and matrix, asked in Amazon and Google interviews.

Problem statement

You are given an m x n grid mat of non-negative integers and an integer threshold.

A square is any k x k block of adjacent cells (k >= 1). Return the largest side length k such that at least one k x k square has a cell sum of at most threshold. Return 0 if even a single cell exceeds the threshold everywhere.

Example 1

Input: mat = [[2,2,5],[2,2,5],[5,5,5]], threshold = 8
Output: 2
Explanation: The top-left 2 x 2 block sums to 8; the whole 3 x 3 grid sums to 33.

Example 2

Input: mat = [[2,3],[4,5]], threshold = 1
Output: 0

Example 3

Input: mat = [[1,1,1],[1,1,1],[1,1,1]], threshold = 9
Output: 3

Constraints

  • 1 <= m, n <= 300
  • 0 <= mat[i][j] <= 10^4
  • 0 <= threshold <= 10^5

Hints for Maximum Side Length of a Square with Sum Less than or Equal to Threshold

  1. Hint 1

    With a 2-D prefix-sum table, the sum of any square is four lookups.

  2. Hint 2

    If some k x k square fits under the threshold, a (k - 1) x (k - 1) square inside it does too — values are non-negative.

  3. Hint 3

    That monotonicity lets you binary-search k, checking every placement of a k x k square per step.

How to solve Maximum Side Length of a Square with Sum Less than or Equal to Threshold

Precompute 2-D prefix sums so any square's sum costs O(1). Feasibility of side k is monotone (shrinking a square never raises its sum), so binary-search the largest feasible k.

Approach

  1. Build P[i][j] = sum of mat[0..i-1][0..j-1] for 0 <= i <= m, 0 <= j <= n.
  2. The square with top-left (i, j) and side k sums to P[i+k][j+k] - P[i][j+k] - P[i+k][j] + P[i][j].
  3. fits(k): true if any placement of a k x k square sums to at most threshold.
  4. Binary-search k in [0, min(m, n)], moving up when fits(mid) holds; k = 0 always fits.

Why it works

Every cell is non-negative, so a sub-square of a fitting square also fits: the predicate fits(k) is true up to some largest k and false after it. Binary search on such a predicate lands exactly on that boundary, and the prefix-sum identity is inclusion–exclusion over four rectangles anchored at the origin.

Complexity

  • Time — O(m · n · log(min(m, n)))
  • Space — O(m · n)

Pitfalls

  • Use the upper-middle (lo + hi + 1) / 2 when moving lo = mid, or the loop never ends.
  • Return 0, not 1, when every single cell is above the threshold.
  • Off-by-one in the prefix table: give it an extra zero row and column.

Reference solution

Python

from typing import List

def maxSideLength(mat: List[List[int]], threshold: int) -> int:
    m, n = len(mat), len(mat[0])
    P = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            P[i + 1][j + 1] = P[i][j + 1] + P[i + 1][j] - P[i][j] + mat[i][j]

    def fits(k):
        for i in range(m - k + 1):
            for j in range(n - k + 1):
                if P[i + k][j + k] - P[i][j + k] - P[i + k][j] + P[i][j] <= threshold:
                    return True
        return False

    lo, hi = 0, min(m, n)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if fits(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

Java

public static int maxSideLength(int[][] mat, int threshold) {
    int m = mat.length, n = mat[0].length;
    int[][] P = new int[m + 1][n + 1];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            P[i + 1][j + 1] = P[i][j + 1] + P[i + 1][j] - P[i][j] + mat[i][j];
    int lo = 0, hi = Math.min(m, n);
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        boolean ok = false;
        for (int i = 0; i + mid <= m && !ok; i++)
            for (int j = 0; j + mid <= n; j++)
                if (P[i + mid][j + mid] - P[i][j + mid] - P[i + mid][j] + P[i][j] <= threshold) { ok = true; break; }
        if (ok) lo = mid; else hi = mid - 1;
    }
    return lo;
}

C++

int maxSideLength(vector<vector<int>>& mat, int threshold) {
    int m = mat.size(), n = mat[0].size();
    vector<vector<int>> P(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            P[i + 1][j + 1] = P[i][j + 1] + P[i + 1][j] - P[i][j] + mat[i][j];
    int lo = 0, hi = min(m, n);
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        bool ok = false;
        for (int i = 0; i + mid <= m && !ok; i++)
            for (int j = 0; j + mid <= n; j++)
                if (P[i + mid][j + mid] - P[i][j + mid] - P[i + mid][j] + P[i][j] <= threshold) { ok = true; break; }
        if (ok) lo = mid; else hi = mid - 1;
    }
    return lo;
}

JavaScript

var maxSideLength = function(mat, threshold) {
    var m = mat.length, n = mat[0].length;
    var P = [];
    for (var i = 0; i <= m; i++) P.push(new Array(n + 1).fill(0));
    for (var r = 0; r < m; r++)
        for (var c = 0; c < n; c++)
            P[r + 1][c + 1] = P[r][c + 1] + P[r + 1][c] - P[r][c] + mat[r][c];
    var fits = function(k) {
        for (var a = 0; a + k <= m; a++)
            for (var b = 0; b + k <= n; b++)
                if (P[a + k][b + k] - P[a][b + k] - P[a + k][b] + P[a][b] <= threshold) return true;
        return false;
    };
    var lo = 0, hi = Math.min(m, n);
    while (lo < hi) {
        var mid = (lo + hi + 1) >> 1;
        if (fits(mid)) lo = mid; else hi = mid - 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search