Teaching Kids Programming – Dynamic Programming Algorithm to Calculate Largest Square Submatrix

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a two-dimensional integer matrix, return the area of the largest square of 1 s.

Constraints
n, m ≤ 200 where n and m are the number of rows and columns in matrix
Example 1
Input

1 2 3 4 5 6 7 8

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

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

Output
16

The bottom left square has a bigger area than the top right square.

Largest Square Submatrix via Bruteforce Algorithm

We can bruteforce the Matrix to check each pixel – this takes O(RC) time where R is the number of rows and C is the number of the columns of the Matrix. If it is a One, we start expanding the square matrix with side N, and check if the sub matrix starting at that position contains all ones.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def largestSquareSubMatrix(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        ans = 0
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 0:
                    continue
                x = 1
                ans = max(ans, 1)
                while r + x < rows and c + x < cols:
                    allOnes = True
                    # check if sub matrix at (r, c) with size x contains all ones?
                    for i in range(x + 1):
                        for j in range(x + 1):
                            if matrix[r + i][c + j] != 1:
                                allOnes = False
                                break
                    if allOnes:
                        ans = max(ans, x + 1)
                    else:
                        break # not possible for bigger size
                    x += 1
        return ans ** 2

class Solution:
    def largestSquareSubMatrix(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        ans = 0
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 0:
                    continue
                x = 1
                ans = max(ans, 1)
                while r + x < rows and c + x < cols:
                    allOnes = True
                    # check if sub matrix at (r, c) with size x contains all ones?
                    for i in range(x + 1):
                        for j in range(x + 1):
                            if matrix[r + i][c + j] != 1:
                                allOnes = False
                                break
                    if allOnes:
                        ans = max(ans, x + 1)
                    else:
                        break # not possible for bigger size
                    x += 1
        return ans ** 2

The time complexity is O(R*R*C*C) as it requires O(RC) to to check if a submatrix contains all ones.

Calculate Largest Square Submatrix via Dynamic Programming Algorithm

The above algorithm takes long time because we repeatedly check if a sub area contains all ones, we can store the intemediate results in a dp array. Let’s use dp[a][b] to represent the largest side of a square matrix that ends at (a, b). Then, we can update the dp array based on its two neighbour values in the up, left, and the one in its northeast diagonals.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def largestSquareSubMatrix(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        dp = [[0 for _ in range(cols)] for _ in range(rows)]
        maxSide = 0
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 0:
                    dp[r][c] = 0
                else:
                    dp[r][c] = 1
                    if r > 0 and c > 0 and matrix[r-1][c] == 1 and matrix[r][c-1] == 1 and matrix[r-1][c-1] == 1:
                        dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r - 1][c - 1]) + 1
                    maxSide = max(maxSide, dp[r][c])
        return maxSide ** 2

class Solution:
    def largestSquareSubMatrix(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        dp = [[0 for _ in range(cols)] for _ in range(rows)]
        maxSide = 0
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 0:
                    dp[r][c] = 0
                else:
                    dp[r][c] = 1
                    if r > 0 and c > 0 and matrix[r-1][c] == 1 and matrix[r][c-1] == 1 and matrix[r-1][c-1] == 1:
                        dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r - 1][c - 1]) + 1
                    maxSide = max(maxSide, dp[r][c])
        return maxSide ** 2

The time complexity is O(RC). The space complexity is O(RC) due to storing a Dynamic Programming array values.

–EOF (The Ultimate Computing & Technology Blog) —