All-Ones Rectangles

Medium

You are given a table grid of 0s and 1s. Count the axis-aligned rectangular blocks in it whose cells are **all** 1. Blocks with different boundaries count separately, even if one lies inside another.

Example 1

grid=[[1, 1], [1, 0]] → 5

Three 1×1 cells, one 1×2 strip in the top row and one 2×1 strip in the left column: 5 in total.

Example 2

grid=[[1, 1, 1]] → 6

Three cells, two strips of length 2 and one of length 3: 6 rectangles.

Example 3

grid=[[0, 1], [1, 1]] → 5

Constraints

1 ≤ rows, columns ≤ 150
grid[i][j] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Array Dynamic Programming Matrix Monotonic Stack

Similar problems

Biggest Solid Panel Block Hard Long Leaps Across a Board Hard Sum of Segment Minimums Medium Tree of Leaf Products Medium Sightlines on the Parade Ground Medium

Input

grid=[[1, 1], [1, 0]]

Expected

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