We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Square Submatrices with All Ones

Number: 1402

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Microsoft

Problem Description

Given an m x n binary matrix (with values 0 and 1), the task is to count the number of square submatrices that have all ones. Each submatrix must be square and completely filled with ones.

Key Insights

  • Use dynamic programming to solve the problem.
  • Create a dp table where each dp[i][j] represents the size of the largest square that ends at cell (i, j).
  • For a cell containing one, the potential square size is determined by taking the minimum of its top, left, and top-left neighbors, then adding one.
  • Accumulate the value of dp[i][j] to get the total count of square submatrices with all ones.
  • Handling boundary conditions where the cell is in the first row or column is essential.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n) (this can be optimized to O(n) if modifying the original matrix is allowed)

Solution

We solve the problem using dynamic programming. For each cell in the matrix that contains a one, we determine the size of the maximal square submatrix ending at that cell by looking at its top, left, and top-left neighbors in the dp table. The cell's dp value will be one plus the minimum of these three values. The final answer is the sum of all values in the dp table, which represent the count of squares ending at each position.

Code Solutions

# Function to count square submatrices with all ones
def countSquares(matrix):
    # Get dimensions of matrix
    rows = len(matrix)
    cols = len(matrix[0])
    total_squares = 0

    # Iterate over each cell in the matrix
    for i in range(rows):
        for j in range(cols):
            # If the cell is not in the first row or first column and is a 1 
            if matrix[i][j] == 1 and i > 0 and j > 0:
                # Determine the size of the largest square ending at (i, j)
                matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]) + 1
            # Add current value to the total count of squares
            total_squares += matrix[i][j]
    return total_squares

# Example usage
example_matrix = [
    [0, 1, 1, 1],
    [1, 1, 1, 1],
    [0, 1, 1, 1]
]
print("Total squares:", countSquares(example_matrix))
← Back to All Questions