Maximal Square
On this page
Problem statement
Given an m × n grid of '0' and '1' characters, return the area of the largest square that contains only '1's. The square's sides are parallel to the grid. If the grid has no '1' at all, return 0.
A 2D dynamic-programming question whose whole difficulty is choosing the right state. Once you define it, the recurrence is one line. Original problem: LeetCode 221.
Example

Input: [["1","0","1","1","1"],
["1","1","1","1","1"],
["0","1","1","1","1"],
["1","1","0","1","1"]]
Output: 9 # side 3
Input: [["0","1"], ["1","0"]] -> 1
Input: [["0"]] -> 0
Constraints (assumed)
- 1 ≤ m, n ≤ 300.
What this question tests
- Defining a DP state on the bottom-right corner of a square.
- Seeing why the answer depends on three neighbours, not two.
- Reducing memory to one row; returning the area, not the side.
Questions to ask first
- Area or side length? (Here: area.)
- Are the cells characters or integers? (Here: the characters '0' and '1'.)
- Square only, or any rectangle? (Here: square. The rectangle version is a harder follow-up.)
- May I modify the grid to store DP values in place?
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.