Corner Blocks Within Budget

Medium

You are given a table of non-negative integers grid and an integer budget. Consider the rectangles that start at the top-left cell (0, 0) and end at any cell (i, j). Count how many of them have a total sum that **does not exceed** budget.

Example 1

grid=[[4, 3, 8], [2, 6, 1]], budget=10 → 3

The corner rectangle sums are 4, 7, 15 in the first row and 6, 15, 24 in the second. Three of them are at most 10.

Example 2

grid=[[0, 0], [0, 5]], budget=4 → 3

Every rectangle except the full one (sum 5) fits the budget.

Example 3

grid=[[9]], budget=3 → 0

Constraints

1 ≤ rows, columns ≤ 1000
0 ≤ grid[i][j] ≤ 1000
1 ≤ budget ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Matrix Prefix Sum

Similar problems

Largest Light Square Medium Neighbourhood Sums in a Grid Medium K-th Largest Corner XOR Medium Three Heaviest Diamonds Medium Balanced Square in a Grid Medium

Input

grid=[[4, 3, 8], [2, 6, 1]], budget=10

Expected

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