Maximal Square Leetcode Problem 221 [Python Solution]

If you've been preparing for coding interviews, you may have come across the Maximal Square problem on LeetCode.

This problem falls under the category of 2-D Dynamic Programming and is considered a medium-level challenge.

Companies like Google have been known to include this problem in their interview processes.

In this blog post, we'll break down the problem, provide an efficient Python solution, and discuss the reasoning behind our approach.

Problem Overview

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

To put it simply, you're given a grid of 0's and 1's, and you need to find the largest square in this grid that is entirely composed of 1's.

The output you need to return is the area of this square.

Here's an example to help you understand the problem better:

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

In this example, the input grid contains a 2×2 square of 1's, and its area is 4. Therefore, the function should return 4.

Understanding Constraints

Before we dive into the solution, it's essential to understand the constraints provided in the problem description:

• m represents the number of rows in the matrix.
• n represents the number of columns in the matrix.
• 1 <= m, n <= 300
• Each element in the matrix can be either '0' or '1'.

Now that we have a clear picture of the problem, let's explore the solution.

Maximal Square LeetCode Problem Solution

We'll provide an efficient Python solution for this problem, but before we do that, let's understand the approach.

Bruteforce Approach

A straightforward approach to solving this problem is to consider each cell in the grid as the top-left corner of a square and attempt to expand the square as much as possible.

Here are the steps for this approach:

1. Iterate through each cell in the grid.
2. If the current cell contains '1', try to expand a square as much as possible by checking the cells to the right, down, and diagonally down-right.
3. Keep track of the maximum square area encountered during the process.
4. Return the square of the maximum side length found.

However, this bruteforce approach is inefficient, with a time complexity of O(m * n * min(m, n)).

We can optimize this solution by using dynamic programming.

An Efficient Approach with Dynamic Programming

Dynamic programming is a powerful technique for solving problems by breaking them down into smaller subproblems and caching the results to avoid redundant computations.

To solve the Maximal Square problem efficiently, we'll use a dynamic programming approach.

Here are the key ideas behind this approach:

1. We'll create a cache to store the maximum side length of the square that can be formed with each cell as the top-left corner.

2. We'll iterate through the grid in a bottom-up manner, starting from the last row and last column.

3. For each cell, we'll check if it contains '1' and calculate the maximum side length of the square that can be formed with this cell as the top-left corner based on the values in the cells to its right, below, and diagonally below-right.

4. We'll update the cache with the calculated maximum side length.

5. Finally, we'll return the square of the maximum side length as the answer.

Here's the Python code that implements this efficient approach:

from typing import List

def maximalSquare(matrix: List[List[str]]) -> int:
    # Get the number of rows and columns in the matrix
    ROWS, COLS = len(matrix), len(matrix[0])

    # Create a cache to store the maximum side length of the square
    cache = {}  # Map each (r, c) -> maxLength of square

    def helper(r, c):
        if r >= ROWS or c >= COLS:
            return 0

        if (r, c) not in cache:
            down = helper(r + 1, c)
            right = helper(r, c + 1)
            diag = helper(r + 1, c + 1)

            cache[(r, c)] = 0

            if matrix[r][c] == "1":
                cache[(r, c)] = 1 + min(down, right, diag)

        return cache[(r, c)]

    helper(0, 0)
    return max(cache.values()) ** 2

The maximalSquare function takes a binary matrix as input and returns the area of the largest square composed of 1's in the grid.

This efficient approach significantly reduces the time complexity to O(m * n) as we only traverse the grid once, and the space complexity is also O(m * n) due to the cache.

Time and Space Complexity

In summary, the dynamic programming approach provides a much more efficient solution to the Maximal Square problem.

Here's a recap of the time and space complexity:

• Time Complexity: O(m * n) – We iterate through the grid once.
• Space Complexity: O(m * n) – The cache stores the maximum side length for each cell in the grid.

Related Interview Questions By Company:

• Two City Scheduling LeetCode
• Coin Change LeetCode
• Design Linked List LeetCode

Related Interview Questions By Category:

• Insert Into A Binary Search Tree LeetCode
• Accounts Merge LeetCode
• Path With Maximum Probability LeetCode

Reasoning Behind Our Approach

The dynamic programming approach used in this solution is based on the idea of breaking down the problem into smaller subproblems and caching the results to avoid redundant computations.

By considering each cell in the grid and calculating the maximum side length of the square that can be formed with that cell as the top-left corner, we build up the solution efficiently.

Our approach optimally handles the constraints of the problem and ensures that we only perform the necessary calculations to find the largest square.

The use of dynamic programming simplifies the problem and leads to a concise and efficient solution.

In summary, we've explored the Maximal Square problem on LeetCode, provided an efficient Python solution, and discussed the reasoning behind our approach.

Understanding the principles of dynamic programming and breaking down problems into smaller subproblems is a valuable skill for tackling complex coding challenges.

We hope this guide has been helpful, and we encourage you to comment, ask questions, make suggestions, and share this content with others who may find it beneficial.

For the full problem description and more details, you can visit the Maximal Square problem on LeetCode.

Thank you for reading, and happy coding!