Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

LeetCode 221: Maximal Square

By Duncan Smith Apr 10 0

A robot looks down at a patio made of overlapping squares

Solutions to LeetCode problems of Medium or higher difficulty often require a key insight. Even once you understand the problem and the general technique required to solve it, there’s no way to implement an efficient solution without it. Fortunately, dynamic programming gives us heuristics that we can use to point towards the required idea. For LeetCode 221: Maximal Square, the key insight requires some geometric intuition. But once you figure that part out, the rest of the problem is straightforward.

The input for Maximal Square is a 2D char array, where each cell contains the character '0' or the character '1' (not the integers 0 and 1). The goal is to find the largest square containing only the character '1', and return its area.

Using our standard approach for dynamic programming problems, we can start with a dp array of the same dimensions as the input array, where each dp[i][j] stores the best solution at that position — maybe the area of the largest square with a corner at (i, j).

As usual with DP solutions, we need to find an approach where combining smaller subproblems gets us the solution to a larger subproblem, and eventually the original problem. For example, consider the area of the largest square with a top left corner at (0, 0). Since we have our memo table dp, we can assume that we know the area of the largest nearby squares. How can we use that information?

To answer this question, we need to realize that:

  • If a cell is 0, it can’t be the corner of a square.

  • If a cell is 1, it might complete a square by filling in the last corner cell. More specifically, if the 1 cell is surrounded by squares whose sides are at least length s, then we can use it to make a square with side length s+1.

This implies that each element in our dp array needs to store the length of a side, not the area of a square. If we fill our dp array row by row from the top left to the bottom right of the input array, then we only need to check three adjacent cells: the cell to the right (East), the cell below (South), and the cell diagonally to the right and down (Southeast). The remaining adjacent cells will have already been checked in previous steps.

This can be tricky to visualize, so I recommend looking at the excellent diagrams by arkaung on LeetCode.

These two rules form the basis of our recursive function. If we want a function maxSide(i, j) to return the side length of the largest square with its top left corner at (i, j), then:

  • If (i, j) is '0', return 0, since (i, j) can’t be part of a square.

  • Otherwise, return 1 + min(maxSide(i+1, j), maxSide(i+1, j+1), maxSide(i, j+1)). This works because we can make a square side one larger than the smallest adjacent side. (See the References section below for a diagram illustrating that rule).

Once we add memoization to avoid repeatedly calculating the length at the same position, we’re done with the maxSide function.

In the main function, we’ll call maxSide for each position in the input matrix, keeping track of the maximum side length. That will give us the best top left corner starting position. Then we can return maxSide * maxSide to calculate the area of the square with that corner.

Pseudocode

matrix = input char array of size m x n containing '0' and '1' values
dp = int array of size m x n

max = 0
for i from 0 to m-1
    for j from 0 to n-1
        max = max(max, maxSide(i, j))

return max * max

function maxSide(int i, int j)
    if i or j are out of bounds, return 0
    if matrix[i][j] == '0', return 0

    if dp[i][j] > 0
        return dp[i][j]

    dp[i][j] = 1 + min(maxSide(i+1, j), maxSide(i, j+1), maxSide(i+1, j+1))

    return dp[i][j]

Optimizations

Optimization 1: As usual, since we only need information about adjacent cells, we can save space by only storing the adjacent row and column rather than the full dp array.

Optimization 2: To avoid the overhead of recursive function calls, we can use a bottom-up approach. If we do that, the adjacent cells we’ll look at will be above, left, and above-left compared to the current cell. We’ll use these cells because, in the bottom-up approach, we need to look back at dp values that we have previously calculated.

References

For a few bottom-up implementations, see Jianchao Li solution on LeetCode.

Here’s another good visual explanation of the key step, showing why we need to use the minimum side length.

(Image credit: DALL·E 3)

For an introduction to this year’s project, see A Project for 2024.

Categories: LeetCode

Prev
Next

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • 2023 in Review: 50 LeetCode Tips
  • 2022 in Review: Content Bots
  • 2021 in Review: Thoughts on Solving Programming Puzzles
  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • Do Coding Bots Mean the End of Coding Interviews? December 31, 2024
  • Another Project for 2024 May 8, 2024
  • Dynamic Programming Wrap-Up May 1, 2024
  • LeetCode 91: Decode Ways April 24, 2024
  • LeetCode 70: Climbing Stairs April 17, 2024
  • LeetCode 221: Maximal Square April 10, 2024
  • Using Dynamic Programming for Maximum Product Subarray April 3, 2024
  • LeetCode 62: Unique Paths March 27, 2024
  • LeetCode 416: Partition Equal Subset Sum March 20, 2024
  • LeetCode 1143: Longest Common Subsequence March 13, 2024
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2025 Duncan Smith