Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Count Square Submatrices

Explore how to count all square submatrices containing only ones in a binary matrix by applying dynamic programming techniques. Understand the state transition and recurrence relations to solve this problem efficiently in O(m×n) time and constant space. This lesson helps you build problem-solving skills for matrix-based DP challenges.

We'll cover the following...

Statement

Given an N ∗ M matrix containing only ones and zeros, count the total number of square submatrices that contain only 1’s.

Example

Consider the input matrix given below. We have a total of 77 square submatrices with all ones, including 66 square matrices of order 1 x 1 and 11 square matrix of order 2 x 2.

Sample input

[
  [1,0,1],
  [1,1,0],
...