Largest Light Square

Medium

You are given a rectangular table grid of non-negative integers and a number limit. Call a square block of the table light if the sum of all its numbers does not exceed limit. Return the side length of the largest light square, or 0 if not even a 1×1 square is light.

Example 1

grid=[[3, 1, 1], [1, 1, 1], [1, 1, 5]], limit=4 → 2

The 2×2 square in the top-right corner is four ones, summing to 4, exactly the limit. The only 3×3 square is the whole grid with sum 15, which is too heavy.

Example 2

grid=[[7, 8], [9, 6]], limit=5 → 0

Even every single cell exceeds 5, so no square fits and the answer is 0.

Constraints

1 ≤ grid.length, grid[i].length ≤ 600
0 ≤ grid[i][j] ≤ 10⁴
0 ≤ limit ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Matrix Prefix Sum

Similar problems

Richest Plot Under the Cap Hard Find in a Row-Chained Grid Medium Shortest Stretch to the Goal Medium Find in a Grid Sorted Both Ways Medium K-th Smallest in a Sorted Grid Medium

Input

grid=[[3, 1, 1], [1, 1, 1], [1, 1, 5]], limit=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.