← Create New Paste

Maximal Square (LeetCode 221): The Three-Neighbor DP Explained

3 views
Given a binary matrix of '0' and '1' characters, find the area of the largest square containing only 1s. It is a classic dynamic programming interview question because the recurrence is short but not obvious, and interviewers can probe whether you understand why it works. Brute force first For each cell, try growing a square with that cell as the top-left corner, checking each new row and column. That costs roughly O((m*n) * min(m,n)^2). It is fine to mention, but move on quickly. Define the state Let dp[i][j] be the side length of the largest all-1 square whose bottom-right corner is at cell (i, j). If matrix[i][j] is '0', dp[i][j] = 0. Otherwise: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) The answer is the square of the largest dp value. Why the minimum of three neighbors? A square of side k ending at (i, j) requires squares of side at least k - 1 ending at the cell above, the cell to the left, and the cell diagonally up-left. Those three squares overlap to cover everything in the k-by-k block except the corner (i, j) itself. If any one of them is smaller, the block has a 0 somewhere, so the limiting neighbor determines the size. Drawing a 3x3 example with the three overlapping 2x2 squares is the clearest way to explain this on a whiteboard. Python def maximal_square(matrix): if not matrix: return 0 m, n = len(matrix), len(matrix[0]) dp = [0] * (n + 1) best = 0 for i in range(1, m + 1): prev_diag = 0 for j in range(1, n + 1): temp = dp[j] if matrix[i-1][j-1] == '1': dp[j] = 1 + min(dp[j], dp[j-1], prev_diag) best = max(best, dp[j]) else: dp[j] = 0 prev_diag = temp return best * best This uses one row of size n + 1 with a padding column so the first row and column need no special cases. Time is O(m*n), space O(n). The variable prev_diag stores the old value of dp[j-1] from the previous row before it gets overwritten, which is the subtle part of the space optimization. Edge cases - All zeros: answer 0. - A single '1': answer 1. - Characters versus integers: the input uses strings, and comparing to 1 instead of '1' is a common bug. - Returning the side instead of the area. Follow-ups interviewers ask "Count all square submatrices of ones" (LeetCode 1277) uses the same dp and sums every dp value. "Largest rectangle of ones" (Maximal Rectangle) needs a different approach, building a histogram per row and using a stack. Knowing why the square trick doesn't extend to rectangles shows real understanding. How to present it Define the state in words before writing code, justify the recurrence with a picture, write the 2D version first if you want safety, then optimize space if time allows. Support during the interview Explaining a recurrence clearly under pressure is a skill of its own. Linkjob AI (https://linkjob.ai) offers real-time help during live job interviews and technical interviews, suggesting hints and structure while you reason through the problem in your own words.
Created Nov 17, 2026 17:29 Expires Nov 17, 2027 17:29