Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Google SWE coding round, one problem the whole session. Dynamic programming on a binary matrix, which I should have been more ready for.

Questions Asked (1)

Given a binary matrix of size m x n, count the total number of square submatrices where every element is 1, across all possible square sizes.

Algorithms & Data Structures

Author's notes

Took me an embarrassingly long time to get past the brute force instinct.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use dynamic programming where dp[i][j] represents the side length of the largest square submatrix ending at (i, j). The total count of all squares is the sum of dp[i][j] over all cells, since each cell contributes squares of sizes 1 through dp[i][j].

Pro tip: Mention that this DP approach is optimal with O(m*n) time and O(n) space if optimized, and that it elegantly handles overlapping subproblems. Also, clarify that the sum of dp values gives the total count because each square of size k ending at a cell implies the existence of squares of all smaller sizes ending at the same cell.

1. Define the DP state

Let dp[i][j] be the side length of the largest square submatrix with all 1s that ends at cell (i, j). This state captures the maximum square size ending at each position.

2. Establish the recurrence relation

If matrix[i][j] == 1, then dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). Otherwise, dp[i][j] = 0. This builds on the fact that a larger square requires smaller squares at the top, left, and top-left.

3. Initialize and iterate

Initialize a DP table of size m x n (or two rows for space optimization). Iterate through the matrix row by row, computing dp values and accumulating the sum of all dp[i][j] values.

4. Return the total count

The sum of all dp[i][j] values equals the total number of square submatrices of all sizes, because each cell with dp value k contributes k squares (sizes 1 to k) ending at that cell.

Key Points to Mention

Dynamic programming state definition: dp[i][j] as the largest square ending at (i, j).
Recurrence relation: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) when matrix[i][j] == 1.
Summing dp values gives the total count of all squares, not just the largest.
Time complexity O(m*n) and space complexity O(m*n) or O(n) with optimization.
Handling edge cases: first row and first column, and cells with 0.
Explanation of why the recurrence works: a square of size k requires squares of size k-1 at three neighboring positions.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.