Count All-One Square Submatrices
Company: Purestorage
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Quick Answer: This question evaluates dynamic programming, matrix traversal, and algorithmic optimization skills for identifying and counting structured patterns in grids.
Constraints
- 0 <= n <= 300
- matrix has n rows and n columns
- Each matrix[i][j] is either 0 or 1
Examples
Input: ([[1, 0, 1], [1, 1, 0], [1, 1, 0]],)
Expected Output: 7
Explanation: There are six 1 x 1 all-one squares and one 2 x 2 square in the bottom-left area.
Input: ([],)
Expected Output: 0
Explanation: An empty matrix contains no submatrices.
Input: ([[0]],)
Expected Output: 0
Explanation: The only cell is 0, so there are no all-one squares.
Input: ([[1, 1], [1, 1]],)
Expected Output: 5
Explanation: There are four 1 x 1 squares and one 2 x 2 square.
Input: ([[1, 1, 1], [1, 1, 1], [0, 1, 1]],)
Expected Output: 11
Explanation: There are eight 1 x 1 squares and three 2 x 2 squares.
Input: ([[1, 1, 1], [1, 1, 1], [1, 1, 1]],)
Expected Output: 14
Explanation: There are nine 1 x 1 squares, four 2 x 2 squares, and one 3 x 3 square.
Hints
- For each cell, think about the size of the largest all-one square that ends at that cell.
- If matrix[i][j] is 1, its square size depends on the cells directly above, directly left, and diagonally up-left.