How should I practice Count All-One Squares?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Count All-One Squares associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Count All-One Squares

Google● MediumNEW GRADONSITE INTERVIEW

Learn

Problem statement

Given a nonempty rectangular binary matrix, return the number of square submatrices whose cells are all 1.

A square uses consecutive rows and consecutive columns. Count each distinct top-left position and side length once, including 1 x 1 squares. Overlapping squares are counted separately. Return a count of squares, rather than the largest area or the sum of their areas.

Function

countSquares(matrix: int[][]) → int

Examples

Example 1

matrix = [[1,1],[1,1]]return = 5

Four1x1 squares and the one2x2 square contribute five squares.

Example 2

matrix = [[1,1,1],[1,1,1]]return = 8

Six1x1 squares and two overlapping2x2 squares are counted.

Example 3

matrix = [[1,0],[0,1]]return = 2

Only the two isolated1 cells are valid squares.

Constraints

1 <= matrix.length, matrix[0].length <= 100.
Every row has the same length.
Every entry is 0 or 1.