221. Maximal Square

Maximal Square (LeetCode 221) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.

How to solve Maximal Square

Maximal Square is a Unique Paths on Grid problem, part of Dynamic Programming (DP) Patterns. Count paths and find optimal paths in grids using 2D dynamic programming.

Work towards the solution in these steps:

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.

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

The Maximal Square solution and editorial walks through the full approach with reference code.

Problem statement

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.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]] Output: 1

Example 3:

Input: matrix = [["0"]] Output: 0

Constraints:

- m == matrix.length

- n == matrix[i].length

- 1 <= m, n <= 300

- matrix[i][j] is '0' or '1'.

Topics and companies

Topics: Array, Dynamic Programming, Matrix.

Reported in interviews at Amazon, IBM, Google, Twitter, ByteDance, Apple.

How to practise Maximal Square on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(m * n) space.

Open Maximal Square in the code editor, or read the Maximal Square editorial for a worked solution with its approach and complexity analysis.

Where Maximal Square sits in the DSA pattern sheet

• Dynamic Programming (DP) Patterns pattern guide
• 2D Array (Unique Paths on Grid) subpattern
• The full DSA patterns sheet

Problems related to Maximal Square

Other problems that use the same 2D Array (Unique Paths on Grid) and Dynamic Programming (DP) Patterns techniques:

• Count Square Submatrices with All Ones — Medium, same subpattern
• Interleaving String — Medium, same subpattern
• Longest Increasing Path in a Matrix — Hard, same subpattern
• Minimum Falling Path Sum — Medium, same subpattern
• Minimum Path Sum — Medium, same subpattern
• Triangle — Medium, same subpattern

Maximal Square FAQ