You're building a map-tile occupancy analyzer for a warehouse robotics team. The warehouse floor is represented as a binary grid — 1 means a tile is occupied/blocked, 0 means it's free. Your task: count how many square submatrices consisting entirely of 1s exist anywhere in the grid. This helps the team estimate how many valid square "staging zones" of any size could theoretically be marked off in already-occupied regions for a different planning exercise.
Example:
matrix = [
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
→ 15 total square submatrices made entirely of 1s (10 of size 1x1, 4 of size 2x2, 1 of size 3x3).
Function signature
int countSquares(vector<vector<int>>& matrix);
Test cases
Input matrix
Output
Explanation
[[0,1,1,1],[1,1,1,1],[0,1,1,1]]
15
10 (1x1) + 4 (2x2) + 1 (3x3)
[[1,0,1],[1,1,0],[1,1,0]]
7
6 (1x1) + 1 (2x2)
[[0,0],[0,0]]
0
No 1s at all
[[1]]
1
Single cell, single 1x1 square
[[1,1],[1,1]]
5
4 (1x1) + 1 (2x2)
[[1,1,1],[1,1,1],[1,1,1]]
14
9 (1x1) + 4 (2x2) + 1 (3x3)
How interviewers phrase it
"Given a binary matrix, count the total number of square submatrices filled entirely with 1s."
"How many distinct all-ones squares (of any size) can you find in this grid?"
This is LeetCode 1277 — a close cousin of "Maximal Square" (LeetCode 221, which asks for the area of the largest square, not the count of all squares). Interviewers often ask one as a follow-up to the other, so be ready to distinguish them clearly.
Clarifying questions to ask
Are 1x1 squares (single cells containing a 1) counted individually? (Yes, standard convention — confirm.)
Is the matrix guaranteed non-empty, and are all rows the same length (proper rectangular grid)?
What are the matrix dimension constraints? (Determines if O(mn) DP is required vs. something even more optimized — for this problem, O(mn) is already optimal and expected.)
Are matrix values guaranteed to be exactly 0 or 1 (no other values to sanitize)?
Follow-ups to expect
"How is this different from 'Maximal Square' (finding the largest single square)?"
"Explain why dp[i][j] (the size of the largest square ending at (i,j)) also directly equals the COUNT of squares ending at (i,j)."
"Can you do this with O(1) extra space instead of O(m*n) for the DP table?"
"What's the recurrence relation, and why does it use min() of the three neighbors?"
"Can you brute-force this first, and what's its complexity vs the DP approach?"
"How would you extend this to count RECTANGULAR (not just square) submatrices of all 1s?"
Practise questions like this with a real engineer
On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.