This is the 26th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Problem description

221. Largest square

In a two-dimensional matrix of ‘0’ and ‘1’, find the largest square containing only ‘1’ and return its area.

Example:

Input: matrix = [[” 1 “, “0”, “1”, “0” and “0”], [” 1 “, “0”, “1”, “1”, “1”], [” 1 “, “1”, “1”, “1”, “1”], [” 1 “, “0”, “0”, “1”, “0”]]

Output: 4

To analyze problems

We all know that the area of a square is equal to the square of the length of the sides. To find the largest square area, first find the length of the sides of the largest square, and then calculate the square.

The most intuitive solution is to use brute force. Specifically, we iterate over each element in the matrix, and each time we encounter a 1, that element is the upper-left corner of the square; Then calculate the maximum possible side length of the square based on the row and column in the upper left corner (each time you add a row below and a column to the right, determine whether the new row and column satisfy all elements of 1).

Let’s look at the implementation of the code.

If len(matrix[0]) == 0 \ or len(matrix[0]) == 0: if len(matrix[0]) == 0 \ Rows, columns = len(matrix), columns = len(matrix[0]) for I in range(rows): for j in range(columns): If matrix[I][j] == '1': Current_edge = min(rows -i, columns -j) for k in range(1, current_edge): Matrix [I + k][j + k] == '0': break for m in range(k): matrix[I + k][j + k] == '0': break for m in range(k): If matrix[I + m][j + m] == '0' or matrix[I + m][j + k] == '0': tag = False; if matrix[I + m][j + k] == '0': tag = False; if matrix[I + m][j + k] == '0': tag = False; Max_length = Max (max_length, k + 1) else: Max_length * max_length return resultCopy the code

The time complexity of the algorithm is O(m * n * min(m, n) ^ 2), where M and n are the number of rows and columns of the matrix. The space complexity is order 1. Obviously, the time complexity of this algorithm is too high. Let’s look at how to optimize the solution.

This is a problem we can solve using dynamic programming. We use dp[I] [j] to represent the maximum side length of the square with (I, j) as the bottom right corner and containing only 1. After finding all dp[I] [j] values, then the maximum is the maximum length of the sides of the square containing only 1 in the matrix, whose square is the area of the largest square. Now let’s see how to solve for dp[I] [j].

For each position (I, j) in the matrix, check its corresponding value.

  • If the position is 0, then dp[I] [j] =0, because the current position cannot be in a square of 1;

  • If the position is 1, the value of dp[I] [j] is determined by the top, left, and upper-left adjacent positions. That is, the value of the current position is equal to the minimum value of the three adjacent position elements plus 1.

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

So let’s look at the boundary conditions. When I =0 or j=0, if the value of position (I,j) in the matrix is 1, then the side length of the matrix with position (I,j) as the lower right corner can only be 1, that is, dp[I] [j] = 1.

When the matrix for the [[” 1 “, “0”, “1”, “0” and “0”], [” 1 “, “0”, “1”, “1”, “1”], [” 1 “, “1”, “1”, “1”, “1”], [” 1 “, “0”, “0”, “1”, “0”]], the state transition matrix as shown in the figure below.

Let’s look at the implementation of the code.

If len(matrix[0]) == 0 \ or len(matrix[0]) == 0: if len(matrix[0]) == 0 \ return 0 max_edge = 0 m, n = len(matrix), Dp = [[0] * n for _ in range(m)] for I in range(m): for j in range(n): If matrix [I] [j] = = '1' : if I = = 0 # boundary conditions or j = = 0: dp [I] [j] = 1 else: dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 max_edge = max(max_edge, Dp [I][j]) # result = max_edge * max_edge return resultCopy the code

The time complexity of the algorithm is O(m*n), where M and n are the rows and columns of the matrix respectively. The space is order m times n.