5 Best Ways to Program to Find Number of Square Submatrices with All Ones in Python

💡 Problem Formulation: The challenge entails writing a Python program to count the number of square submatrices within a binary matrix that are composed entirely of 1s. Considering a binary matrix as input, such as:

[[0,1,1,1],[1,1,1,1],[0,1,1,1]]

, the desired output would be 15 because there are 10 submatrices of size 1×1, 4 of size 2×2, and 1 of size 3×3, totaling 15 square submatrices with all elements equal to 1.

Method 1: Dynamic Programming

This method utilizes dynamic programming to optimize the counting of square submatrices. For each cell in the matrix, we determine the size of the largest square submatrix ending at this cell, which also contributes to the number of submatrices with all ones. This method is efficient and avoids redundant calculations.

Here’s an example:

def countSquares(matrix):
    count = 0
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] and i and j:
                matrix[i][j] += min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1])
            count += matrix[i][j]
    return count

matrix = [[0,1,1,1], [1,1,1,1], [0,1,1,1]]
print(countSquares(matrix))

Output:

This code iteratively updates the input matrix by using each cell as a potential bottom-right corner of a square matrix, and then adding to the total count. The function first checks if the current item is 1 and not on the first row or column. Then it updates the current cell’s value to 1 plus the minimum of the cell above, to the left, and the top-left diagonal. The count sums up these values.

Method 2: Brute Force

The brute force approach involves checking each possible square matrix within the larger matrix to confirm if it’s comprised of all ones. This method is straightforward and doesn’t require advanced programming techniques; however, it’s not recommended for large matrices due to its high complexity.

Here’s an example:

def isAllOnes(matrix, x, y, size):
    for i in range(x, x + size):
        for j in range(y, y + size):
            if matrix[i][j] == 0:
                return False
    return True

def countSquares(matrix):
    count = 0
    for size in range(1, min(len(matrix), len(matrix[0])) + 1):
        for i in range(len(matrix) - size + 1):
            for j in range(len(matrix[0]) - size + 1):
                if isAllOnes(matrix, i, j, size):
                    count += 1
    return count

matrix = [[0,1,1,1], [1,1,1,1], [0,1,1,1]]
print(countSquares(matrix))

Output:

This code snippet explores all possible starting points for square submatrices (i, j) and all possible sizes of squares. It applies a helper function isAllOnes() to check whether every cell within the potential square contains a 1. If the square contains all ones, it increments the count.

Method 3: Improved Brute Force with Early Stopping

This method improves the brute force technique by adding an early stopping condition when a zero is found within a potential submatrix, thus preventing unnecessary checks. It still suffers from high complexity, but with certain inputs, it might outperform the plain brute force approach.

Here’s an example:

def countSquares(matrix):
    def checkSquare(x, y, size):
        for i in range(x, x+size):
            for j in range(y, y+size):
                if matrix[i][j] == 0:
                    return False
        return True

    n, m = len(matrix), len(matrix[0])
    count = 0
    for size in range(1, min(n, m) + 1):
        for i in range(n - size + 1):
            for j in range(m - size + 1):
                if checkSquare(i, j, size):
                    count += 1
    return count

matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
print(countSquares(matrix))

Output:

The code defines a function called checkSquare() to verify if a square of a certain size starting from a point (x, y) contains all ones. It then iterates over all potential top-left points and sizes, counting each valid square. The early stop occurs once a 0 is found within the checked area.

Method 4: Recursion with Memoization

This technique uses a recursive traversal of the matrix combined with memoization to store the results of subproblems, thus avoiding repeated work. Although conceptually elegant and robust, it can be slower and require more memory than dynamic programming for large inputs.

Here’s an example:

def countSquares(matrix):
    def helper(x, y):
        if x >= len(matrix) or y >= len(matrix[0]):
            return 0
        if memo[x][y] != -1:
            return memo[x][y]
        right = helper(x, y+1)
        down = helper(x+1, y)
        diag = helper(x+1, y+1)
        memo[x][y] = 1 + min(right, down, diag) if matrix[x][y] == 1 else 0
        return memo[x][y]
    
    memo = [[-1]*len(matrix[0]) for _ in range(len(matrix))]
    count = sum(helper(i, j) for i in range(len(matrix)) for j in range(len(matrix[0])))
    return count

matrix = [[0,1,1,1], [1,1,1,1], [0,1,1,1]]
print(countSquares(matrix))

Output:

The recursive function helper() explores the matrix and counts the number of square submatrices with all ones, using a memoization array to store previously computed values. This array essentially acts as a dynamic programming table, with the added overhead of recursive function calls.

Bonus One-Liner Method 5: List Comprehension with Numpy

For those who prefer a more concise and Pythonic approach when working with arrays, assuming you’re okay with including the numpy library, a one-liner list comprehension can succinctly express the count using numpy array operations.

Here’s an example:

import numpy as np

def countSquares(matrix):
    mat = np.array(matrix)
    count = sum((mat[i:, j:])[:min(mat.shape)-i, :min(mat.shape)-j].all() for i in range(mat.shape[0]) for j in range(mat.shape[1]))
    return count

matrix = [[0,1,1,1], [1,1,1,1], [0,1,1,1]]
print(countSquares(matrix))

Output:

This one-liner makes use of numpy’s slicing and all() function. The sum iterates over all cells in the matrix and at each cell (i,j), it slices the matrix into a submatrix from that cell to the end. It checks if all the elements in the submatrix are truthful up to the smallest dimension size, then sums up these booleans to get the count of squares with all ones.

Summary/Discussion

Method 1:

Method 2:

Method 3:

Method 4:

Bonus Method 5: