Maximal Square DP in under 60 seconds

You have a binary matrix full of zeros and ones. Find the largest square made entirely of ones. What's its area?

Brute force means checking every possible square from every possible top-left corner. For each cell, you try every size. That's O(n cubed) at minimum, and it gets ugly fast on large grids.

Dynamic programming cuts that down to a single pass.

Define dp\[i\]\[j\] as the side length of the largest square whose bottom-right corner lands at cell i, j. If that cell is a zero, the answer is zero. If it's a one, look at three neighbors: the cell above, the cell to the left, and the cell diagonally up-left. Take the minimum of those three values and add one.

That minimum is the bottleneck. Your square can only be as big as the smallest square your three neighbors can form. The diagonal handles width and height together.

Fill the table left to right, top to bottom. Track the running maximum. The answer is that maximum squared.

O(n squared) time. O(n) space if you only keep the previous row.

This problem shows up at Google, Amazon, and Meta. The recurrence is the whole trick. If you can explain why it's the minimum of three neighbors, not just one, you're showing real DP intuition.

Full breakdown with visualizations at hellointerview.com/learn/code/dynamic-programming/maximal-square #shorts

Видео Maximal Square DP in under 60 seconds канала Hello Interview