Counting All-Ones Squares

Medium

You get an m × n matrix grid of zeros and ones. Return how many square submatrices of any size consist entirely of 1s. Squares of different sizes or positions are counted separately, even when they overlap.

Example 1

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

There are 7 squares of side 1 and two all-ones 2 × 2 squares, in the top-left and bottom-right corners: 9 in total.

Example 2

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

A single row only fits 1 × 1 squares, one for each 1.

Example 3

grid=[[1, 1, 1], [1, 1, 1], [1, 1, 1]] → 14

Constraints

1 ≤ m, n ≤ 300
grid[i][j] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Matrix

Similar problems

Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium Largest Solid Square Medium Best Spot for the Turret Medium Steps to the Nearest Zero Medium

Input

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

Expected

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