## Maximal Square

###### DESCRIPTION (credit Leetcode.com)

Given an m x n 2D matrix with only 0's and 1's, write a function to return the area of the largest square containing only 1's.

###### EXAMPLES

Input:

`matrix = [ [0, 0, 1, 0, 0], [1, 1, 1, 0, 1], [0, 1, 1, 0, 0] ]`

Output:

`4`

Run your code to see results here

## Explanation

The solution uses **bottom-up dynamic programming** to solve the problem. The solution is based on the observation that the size of the largest square ending (bottom-right corner) at a particular cell is equal to the minimum of the sizes of the largest squares ending at the three adjacent cells plus 1.

We create a 2D integer array dp of size (r + 1) x (c + 1) where r is the number of rows in the input array and c is the size of each row. dp[i][j] stores the side length of the largest square ending at the cell matrix[i - 1][j - 1]. All elements of dp are initialized to 0.

def maximal_square(matrix):if not matrix:return 0r = len(matrix)c = len(matrix[0])dp = [[0] * (c + 1) for _ in range(r + 1)]max_side = 0for i in range(1, r + 1):for j in range(1, c + 1):if matrix[i - 1][j - 1] == 1:top = dp[i - 1][j]left = dp[i][j - 1]diag = dp[i - 1][j - 1]dp[i][j] = min(top, left, diag) + 1max_side = max(max_side, dp[i][j])return max_side * max_side

We then use a nested loop to iterate over the input array. For each cell matrix[i - 1][j - 1], we check if the cell contains a 1. If it does, we update dp[i][j] to the minimum of the sizes of the largest squares ending at the three adjacent cells plus 1. We also update a variable max_side to store the maximum side length of the largest square we have found so far.

def maximal_square(matrix):if not matrix:return 0r = len(matrix)c = len(matrix[0])dp = [[0] * (c + 1) for _ in range(r + 1)]max_side = 0for i in range(1, r + 1):for j in range(1, c + 1):if matrix[i - 1][j - 1] == 1:top = dp[i - 1][j]left = dp[i][j - 1]diag = dp[i - 1][j - 1]dp[i][j] = min(top, left, diag) + 1max_side = max(max_side, dp[i][j])return max_side * max_side

def maximal_square(matrix):if not matrix:return 0r = len(matrix)c = len(matrix[0])dp = [[0] * (c + 1) for _ in range(r + 1)]max_side = 0for i in range(1, r + 1):for j in range(1, c + 1):if matrix[i - 1][j - 1] == 1:top = dp[i - 1][j]left = dp[i][j - 1]diag = dp[i - 1][j - 1]dp[i][j] = min(top, left, diag) + 1max_side = max(max_side, dp[i][j])return max_side * max_side

At the end of the loop, max_side contains the side length of the largest square containing only 1's in the input array. The area of the square is max_side * max_side.

## Solution

def maximal_square(matrix):if not matrix:return 0r = len(matrix)c = len(matrix[0])dp = [[0] * (c + 1) for _ in range(r + 1)]max_side = 0for i in range(1, r + 1):for j in range(1, c + 1):if matrix[i - 1][j - 1] == 1:top = dp[i - 1][j]left = dp[i][j - 1]diag = dp[i - 1][j - 1]dp[i][j] = min(top, left, diag) + 1max_side = max(max_side, dp[i][j])return max_side * max_side

## Complexity Analysis

**Time Complexity**: We iterate over each cell of the input array once, and for each cell, we perform a constant amount of work. Therefore, the time complexity is O(m * n) where m is the number of rows in the input array and n is the length of each row.
**Space Complexity**: We use a 2D array dp of size (m + 1) x (n + 1) to store the side length of the largest square ending at each cell. Therefore, the space complexity is O(m * n).

Loading comments...