[00:01] programming, this problem might just humble you. You're given a grid of zeros and ones, and you have to find the largest square made of only ones. Most people try checking every possible square, but that can get really messy
[00:13] fast. Instead, what if you pick any cell with value one? Then try to find what's the largest square we can build ending here. A square doesn't just depend on one direction, it depends on three: top, left, and diagonal. This is because a
[00:27] square needs equal height, width, and a filled interior. Now, suppose top and left each give you a square of size three, but diagonal only gives you two. Can you build a 4x4 square? No, because the interior can't support it. So, the
[00:41] square you build here is only as big as the smallest neighbor cell can make. That's why we take minimum of top, left, diagonal plus one. Now, watch what happens. As you scan the grid, each cell builds on previous ones. Small squares
[00:55] largest possible square. You didn't check every square, you built off past Want to learn more about DP problems? Like the video and follow.