Count Square Submatrices with All Ones

Count Square Submatrices with All Ones is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.

Problem statement

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

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. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = [ [1,0,1], [1,1,0], [1,1,0] ] Output: 7 Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 + 1 = 7.

Constraints:

- 1 <= arr.length <= 300

- 1 <= arr[0].length <= 300

- 0 <= arr[i][j] <= 1

Topics and companies

Topics: Array, Dynamic Programming, Matrix.

Reported in interviews at Google, Amazon.

How to practise Count Square Submatrices with All Ones on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(1) space.

Open Count Square Submatrices with All Ones in the code editor, or read the Count Square Submatrices with All Ones editorial for a worked solution with its approach and complexity analysis.

Where Count Square Submatrices with All Ones sits in the DSA pattern sheet

Problems related to Count Square Submatrices with All Ones

Other problems that use the same 2D Array (Unique Paths on Grid) and Dynamic Programming (DP) Patterns techniques:

Opening the problem

Progress is saved as you study.