MediumArraysAI interview only
Count Square Submatrices with All Ones
Asked atgoogleamazonmicrosoftapple
01 · Problem
Given an m x n matrix matrix containing only 0s and 1s, return how many square submatrices consist entirely of 1s.
Squares of every size count, and overlapping squares are counted separately (a single 1 cell is a 1x1 square).
02 · Examples
Example 01
Input
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
Output
15
There are 10 squares of size 1, 4 squares of size 2 and 1 square of size 3, for a total of 15.
Example 02
Input
matrix = [[1,0,1],[1,1,0],[1,1,0]]
Output
7
There are 6 squares of size 1 and 1 square of size 2 (bottom-left), for a total of 7.
Example 03
Input
matrix = [[0,0],[0,0]]
Output
0
No cell is 1, so there are no squares.
03 · Constraints
- 011 <= matrix.length <= 300
- 021 <= matrix[0].length <= 300
- 03matrix[i][j] is 0 or 1
04 · Optimal complexity
- Time
- O(m * n)
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.