---
title: 'Maximal Square DP in Under 60 Seconds'
source: 'https://youtube.com/watch?v=H_JCFKfNA5s'
video_id: 'H_JCFKfNA5s'
date: 2026-08-04
duration_sec: 66
---

# Maximal Square DP in Under 60 Seconds

> Source: [Maximal Square DP in Under 60 Seconds](https://youtube.com/watch?v=H_JCFKfNA5s)

## Summary

This video explains the dynamic programming approach to solving the Maximal Square problem, where the goal is to find the largest square of ones in a binary grid. It highlights the key insight of using the minimum of top, left, and diagonal neighbors to build larger squares efficiently.

### Key Points

- **Problem Definition** [00:01] — Given a grid of zeros and ones, find the largest square made only of ones. Brute force checking every square is messy and inefficient.
- **DP Insight** [00:13] — For any cell with value one, the largest square ending there depends on three directions: top, left, and diagonal. This is because a square needs equal height, width, and a filled interior.
- **Limitation Example** [00:27] — If top and left each give a square of size three, but diagonal only gives two, you cannot build a 4x4 square because the interior can't support it. The square size is limited by the smallest neighbor.
- **DP Formula** [00:41] — The size of the square at a cell is the minimum of top, left, and diagonal plus one. This formula builds on previous computations.
- **Efficiency** [00:55] — By scanning the grid and building off past results, you avoid checking every square, achieving an efficient solution.

### Conclusion

The video demonstrates that dynamic programming offers an elegant and efficient solution to the Maximal Square problem by leveraging the minimum of three neighboring cells, avoiding brute force enumeration.

## Transcript

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
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
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
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
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.