221. Maximal Square

How to solve Maximal Square (LeetCode 221): the approach in brief

The problem

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Pattern

Maximal Square is a Dynamic Programming (DP) Patterns problem, in the 2D Array (Unique Paths on Grid) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Count paths and find optimal paths in grids using 2D dynamic programming.

Approach outline

1. Consider using dynamic programming to efficiently compute the largest square ending at each cell.
2. Think about how the value at each cell depends on its neighboring cells to the left, top, and top-left.
3. If the current cell contains '1', its maximal square size is limited by the minimal square sizes of those three neighbors plus one.

Complexity

The reference solution runs in O(m * n) time and O(m * n) space.

Asked at

Maximal Square has been reported in interviews at Amazon, IBM, Google, Twitter, ByteDance, Apple.