Skip to main content

1277. Count Square Submatrices with All Ones

medium

Given a 0/1 matrix, count all square submatrices entirely of 1s. The classic 'max square at (i, j)' DP doubles as a counter — sum every cell's largest-square value.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Constraints

  • 1 <= arr.length <= 300
  • 1 <= arr[0].length <= 300
  • 0 <= arr[i][j] <= 1

Examples

Example 1

Input
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
Output
15

Explanation: There are 10 squares of side 1, 4 squares of side 2, 1 square of side 3. Total = 15.

Example 2

Input
matrix = [[1,0,1],[1,1,0],[1,1,0]]
Output
7

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If dp[i][j] = side length of the largest all-1 square with bottom-right corner at (i, j), that's also the count of squares ending at (i, j).

Hint 2

Recurrence on 1-cells: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

Hint 3

Answer = sum of dp[i][j] over the whole grid.

Solution approach

Reveal approach

Define the subproblem dp[i][j] = the side length of the largest all-1 square whose bottom-right corner is (i, j). This value equals the number of distinct squares ending at that corner (one of each side from 1 up to dp[i][j]). The recurrence relation is dp[i][j] = 0 if matrix[i][j] == 0, else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) — a square of side s ending here requires that s-1 squares exist above, left, and on the diagonal. Base case: cells in row 0 or column 0 with matrix[i][j] == 1 contribute dp[i][j] = 1. Sum dp over the whole grid for the answer. You can update the matrix in place to save memory, or roll two rows. O(m * n) time, O(m * n) or O(min(m, n)) space.

Complexity

Time
O(m * n)
Space
O(m * n)

Related patterns

  • dynamic-programming
  • memoization-recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Count Square Submatrices with All Ones and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →