Skip to main content
Talentd

Maximum Side Length of a Square with Sum Less than or Equal to Threshold - Solution & Explanation

MediumArrayBinary SearchMatrixPrefix Sum21 min readAsked at: Amazon, Google, IMC +1
Practice this problem

Problem Statement

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.

 

Example 1:

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
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

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

 

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 300
  • 0 <= mat[i][j] <= 104
  • 0 <= threshold <= 105

Approach Overview

Problem Overview: You are given an m x n matrix and a threshold. The task is to find the largest possible square submatrix whose total sum is less than or equal to the threshold. The result is the side length of that square.

Approach 1: Prefix Sum + Iteration (Time: O(m * n * min(m,n)), Space: O(m * n))

This approach builds a 2D prefix sum matrix so you can query the sum of any square in constant time. After preprocessing, iterate through each cell and attempt to expand the square size from that position. Using the prefix matrix, compute the sum of a candidate square with the formula sum(x1,y1,x2,y2) in O(1). Continue increasing the side length while the square sum remains ≤ threshold. This method is straightforward and demonstrates correct use of prefix sums, but it checks many possible square sizes.

Approach 2: Binary Search on Side Length (Time: O(m * n * log(min(m,n))), Space: O(m * n))

This approach still relies on a 2D prefix sum but reduces unnecessary checks using binary search. Instead of testing every square size, search the possible side length range from 0 to min(m,n). For a candidate size k, scan the matrix and use the prefix sum to compute each k×k square sum in O(1). If any square satisfies the threshold constraint, the size is valid and you try a larger one. Otherwise, search smaller sizes. The monotonic property (if size k works, all smaller sizes work) makes binary search effective.

The prefix matrix itself is computed in O(m*n) using cumulative sums from the matrix. Each square sum query becomes a constant-time subtraction of four prefix values.

Recommended for interviews: Binary search with prefix sum is the approach most interviewers expect. A brute-force square scan shows you understand the problem, but combining prefix sums with binary search demonstrates algorithmic optimization and familiarity with matrix range queries.

Approach 1: Using Prefix Sum and Iteration

This approach involves calculating the prefix sum matrix which allows for constant time computation of any sub-matrix sum. We then iterate over possible top-left corners for squares and check if the sum of the square area does not exceed the threshold using the prefix sum matrix.

This solution computes a prefix sum matrix of size (m+1)x(n+1). It then iterates over each possible starting point and potential square sizes contained within the matrix. The prefixed summed values allow for rapid calculation of the sum for any rectilinear sub-section of the matrix.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m*n*k) where k is constrained by min(m, n) and bounded by the success of squares.
Space Complexity: O(m*n)

Try this approach in the editor →

Approach 2: Binary Search on Side Length

This approach utilizes binary search to find the maximum possible size of a square whose sum does not exceed the given threshold. It initially calculates a prefix sum matrix and then performs binary search based on potential square side lengths.

This C implementation uses a binary search on the possible side lengths to efficiently determine if a square of that side can have a sum less than or equal to the threshold. The helper function isValid checks if the sum of the square area from the prefix sum matrix fits within the given threshold.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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

Try this approach in the editor →

Approach 3: 2D Prefix Sum + Binary Search

We can precompute a 2D prefix sum array s, where s[i + 1][j + 1] represents the sum of elements in the matrix mat from (0, 0) to (i, j). With this, we can calculate the sum of elements in any square region in O(1) time.

Next, we can use binary search to find the maximum side length. We enumerate the side length k of the square, and then iterate through all possible top-left positions (i, j) of the square. We can calculate the sum of elements v for the square. If v leq threshold, it indicates that there exists a square region with side length k whose sum is less than or equal to the threshold; otherwise, no such square exists for the current k.

The time complexity is O(m times n times log min(m, n)), and the space complexity is O(m times n).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Prefix Sum and Iteration

Time Complexity: O(m*n*k) where k is constrained by min(m, n) and bounded by the success of squares.
Space Complexity: O(m*n)

Binary Search on Side Length

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

2D Prefix Sum + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix Sum + IterationO(m * n * min(m,n))O(m * n)When implementing a straightforward solution using prefix sums without optimization
Binary Search on Side Length + Prefix SumO(m * n * log(min(m,n)))O(m * n)Preferred approach when matrix dimensions are large and you want fewer square checks

Video Solution

Maximum Side Length of a Square with Sum Less than or Equal to Threshold | 2 Ways | Leetcode 1292 • codestorywithMIK • 10,504 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Side Length of a Square with Sum Less than or Equal to Threshold easy or hard?
The problem is rated Medium because it requires combining two concepts: 2D prefix sums and binary search optimization. Developers comfortable with matrix prefix sums can implement the base solution quickly, while the optimized version requires recognizing the monotonic property of square sizes.
Maximum Side Length of a Square with Sum Less than or Equal to Threshold Python/Java solution
Implementations typically build a prefix sum matrix first, then either iterate through square sizes or apply binary search. The same logic works across Python, Java, C++, and JavaScript because the algorithm relies on simple array operations and constant-time prefix calculations.
How to solve Maximum Side Length of a Square with Sum Less than or Equal to Threshold in O(m*n log n)?
First compute a 2D prefix sum so any square sum can be calculated in O(1). Then binary search the side length between 0 and min(m,n). For each candidate size, scan the matrix and check all k×k squares using the prefix matrix. If a valid square exists, increase the size; otherwise decrease it.
What is the best approach for Maximum Side Length of a Square with Sum Less than or Equal to Threshold?
The most efficient approach combines a 2D prefix sum with binary search on the square side length. The prefix sum allows constant-time submatrix sum queries, and binary search reduces the number of candidate square sizes. This results in O(m * n * log(min(m,n))) time and O(m * n) space.
Is Maximum Side Length of a Square with Sum Less than or Equal to Threshold asked at Google/Amazon/Meta?
Matrix prefix sum and submatrix query problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test understanding of 2D prefix sums, matrix traversal, and optimization with binary search.
What data structure is used in Maximum Side Length of a Square with Sum Less than or Equal to Threshold?
The key data structure is a 2D prefix sum array. It stores cumulative sums so the sum of any submatrix can be computed with four lookups. The algorithm also uses binary search to efficiently determine the maximum valid square size.
What is the time complexity of Maximum Side Length of a Square with Sum Less than or Equal to Threshold?
The optimal solution runs in O(m * n * log(min(m,n))) time using binary search on the side length and prefix sums for constant-time square sum checks. Building the prefix sum matrix takes O(m * n) time and space.

Ready to solve this problem?

Practice Maximum Side Length of a Square with Sum Less than or Equal to Threshold with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays