Maximal Square

Problem

Qn - Maximal Square You’re given a 2D binary matrix filled with '0' and '1'.
The task is to find the area of the largest square consisting entirely of '1's anywhere in the matrix.
Return that area (side length × side length).

Approach

My first approach was derived from the observation that we can form multiple 2x2 squares and combine them to form a bigger square. So I created a helper function that checks if a 2x2 square of 1s can be formed. We will then memoize this function and create another function which continuously queries the 2x2 helper function with the perimeter cells as params, to check if a 2x2 square can be formed at the perimeter of an existing square. If all of the perimeter cells can form a 2x2 square, it means that we can further expand the square. Well, but if you realise carefully, we are essentially just checking the perimeter of an existing square if we can expand, which doesn’t really make use of the dp. Essentially we require an O(n) operation for every O(n^2) iteration through the matrix. Giving us a runtime of O(n^3)

After consulting ChatGPT, I realised that we can just tweak our solution a little. Instead of creating a dp to return a boolean if a 2x2 square can be formed, we should create a dp to return the largest square that can be formed with that coordinate as the top left corner of the square. In this way, if we memoize it, we will require at most O(n^2) runtime as the dp result will immediately return the answer.

Complexity

• Time: O(m x n)
• Space: O(m x n)

Code

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        longest_len = 0
 
        # given the r,c find the longest length square that can be formed
        # with that coords as the top left corner of the square
        @lru_cache(None)
        def dp(r,c):
            nonlocal longest_len
            # base cases
            if r >= rows or c >= cols: return 0
            if matrix[r][c] == "0": return 0
 
            # recursive case
            res = 1 + min(dp(r+1,c), dp(r,c+1), dp(r+1,c+1))
            longest_len = max(longest_len, res)
            return res
        
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == "1": dp(r,c)
 
        return longest_len ** 2
 

The first approach

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        max_area = 0
 
        # given a coord, return True if it can form a 2x2 square
        # with that coord as the top left corner of the square
        @lru_cache(None)
        def is_2x2_square(r,c):
            if r+1 >= rows or c+1 >= cols: return False
            return matrix[r][c] == "1" and matrix[r+1][c] == "1" and matrix[r][c+1] == "1" and matrix[r+1][c+1] == "1"
 
        # given a coord that has val 1, check if it can expand futher
        # return the largest area it can expand to
        def max_expand_area(r,c):
            curr_len = 1
            to_explore_set = {(r,c)}
 
            while True:
                for curr_r, curr_c in to_explore_set:
                    if not is_2x2_square(curr_r,curr_c): return curr_len ** 2
                new_explore_set = set()
                for i in range(curr_len+1):
                    new_explore_set.add((r+curr_len, c+i))
                    new_explore_set.add((r+i, c+curr_len))
                curr_len += 1
                to_explore_set = new_explore_set
 
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == "1":
                    max_area = max(max_expand_area(r,c), max_area)
 
        return max_area