Show problems as
Classic problem #1277MediumArrayDynamic ProgrammingMatrix

Count Square Submatrices with All Ones

Real-world version: Working Square Blocks on the Solar Array
Tracked in this browser only
Read Count Square Submatrices with All Ones on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A solar array is laid out as a rectangular grid of panels. panels[r][c] is 1 when the panel in row r, column c is generating and 0 when it is dead.

A working block is any square patch of the grid, lined up with the rows and columns, in which every panel is generating. Its side may be any length from one panel upwards, and two working blocks count separately whenever their positions or sides differ, even where they overlap.

Return the total number of working blocks in the array.

Examples

Example 1

Input
panels = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output
8

Eight panels are generating, each giving a working block of side one. The dead panel in the middle falls inside every possible larger square, so nothing bigger counts.

Example 2

Input
panels = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
Output
14

Nine blocks of side one, four of side two and one of side three all count here.

Example 3

Input
panels = [[1, 1, 0, 1], [1, 1, 1, 1], [0, 1, 1, 1]]
Output
13

Ten panels are generating. Three squares of side two also fit: one in the top-left corner and two more across the lower right of the array.

Constraints

  • 1 <= panels.length <= 300
  • 1 <= panels[0].length <= 300
  • 0 <= panels[r][c] <= 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_working_squares(panels: list[list[int]]) -> int:
Java
public int countWorkingSquares(int[][] panels)

More on the same topics