Jobs

Interviews

Discussions

Count Square Submatrices with All Ones

Medium

Asked by:

12 views

Topics:

ArraysDynamic Programming

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

Count Square Submatrices with All Ones

Medium

Asked by:

12 views

Topics:

ArraysDynamic Programming

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions (rows and columns) constraints for the input matrix? Can the matrix be empty?
Can the input matrix contain values other than 0 and 1?
Could you provide a small example to illustrate the expected output for a given matrix?
If the matrix contains no square submatrices with all 1s, what should the return value be (e.g., 0, null, an error)?
Does the square submatrix have to be contiguous, or can it be formed by selecting elements from different rows and columns?

Brute Force Solution

Approach

Imagine you have a grid of squares, some filled with 1s and some with 0s. We want to find all the square shapes inside the grid that are completely filled with 1s. The brute force method is like checking every possible square, one by one, to see if it works.

Here's how the algorithm would work step-by-step:

Start by considering the smallest possible squares: squares that are just a single square from the grid.
Check if each of these tiny squares contains a 1. If it does, count it.
Now, consider squares of size 2x2. Look at every possible location in the grid where a 2x2 square could fit.
For each possible 2x2 square, check if all four squares inside it contain a 1. If they do, count it.
Repeat this process for larger and larger squares: 3x3, 4x4, and so on, until you reach the maximum possible size of a square that could fit within the original grid.
Each time, you check every possible location for that size square and see if all squares inside contain a 1.
Add up the counts from each square size to get the total number of square submatrices that contain all 1s.

Code Implementation

def count_square_submatrices_brute_force(matrix):
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    total_square_count = 0

    # Iterate through all possible square sizes
    for square_side in range(1, min(rows, cols) + 1):
        # Iterate through the matrix to check each possible top-left corner.
        for row_start in range(rows - square_side + 1):
            for col_start in range(cols - square_side + 1):
                is_all_ones = True

                # Check if the current square has all ones
                for row_index in range(row_start, row_start + square_side):
                    for col_index in range(col_start, col_start + square_side):
                        if matrix[row_index][col_index] == 0:
                            is_all_ones = False
                            break
                    if not is_all_ones:
                        break

                # Increment the count if the square contains all ones
                if is_all_ones:
                    total_square_count += 1

    return total_square_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible square submatrix sizes, from 1x1 up to min(rows, cols), let's denote min(rows, cols) as k. For each size, it iterates through all possible top-left corners of the submatrix within the grid, which takes O(rows * cols) time. For each submatrix, it checks if all elements are 1, which takes O(size^2) time. Since rows and cols can be expressed as n, this leads to O(k * n^2 * k^2) overall operations. In the worst case where k is proportional to n, this simplifies to O(n^3).

Space Complexity

O(1) – The provided plain English explanation does not describe the creation of any auxiliary data structures like arrays, lists, or hash maps. It only outlines a process of iterating through the input grid and checking submatrices. Therefore, the space complexity is constant, as no additional memory is allocated based on the size of the input matrix.

Optimal Solution

Approach

The core idea is to avoid redundant calculations by building up square sizes from smaller ones. We use the input grid to store the size of the largest square ending at each cell. This way, we only need to check a few neighbors to decide the size of a larger square.

Here's how the algorithm would work step-by-step:

Look at each number in the grid, one by one.
If the current number is zero, then the largest square that ends here has size zero. We don't need to do anything.
If the current number is one, then the size of the largest square that ends here depends on its three neighbors: the one above, the one to the left, and the one diagonally above and to the left.
Take the smallest of those three neighbors. Add one to that smallest value. This gives the size of the largest square ending at the current number.
Update the current number with this new value (the size of the largest square).
Keep track of the total size of all squares you've found along the way. This is the sum of all the updated values in the grid.
Once you've looked at every number, the total size is the answer: the number of square submatrices with all ones.

Code Implementation

def count_squares(matrix):
    total_square_count = 0
    rows = len(matrix)
    columns = len(matrix[0])

    for row_index in range(rows):
        for column_index in range(columns):
            if matrix[row_index][column_index] == 1:
                # Find min of neighbors to determine square size.
                if row_index > 0 and column_index > 0:

                    matrix[row_index][column_index] = min(
                        matrix[row_index - 1][column_index],
                        matrix[row_index][column_index - 1],
                        matrix[row_index - 1][column_index - 1]
                    ) + 1

                # Add current square size to overall count.
                total_square_count += matrix[row_index][column_index]

    return total_square_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m*n) – The solution iterates through each cell of the input grid once, where the grid has dimensions m rows and n columns. For each cell, a constant number of operations are performed: checking if the cell value is one or zero, and if it's one, finding the minimum of its three neighbors and updating the cell's value. Since the work done for each cell is constant, the overall time complexity is directly proportional to the number of cells in the grid, resulting in a time complexity of O(m*n).

Space Complexity

O(1) – The algorithm operates directly on the input grid, modifying its values in place. No additional data structures like lists, sets, or maps are created to store intermediate results beyond the modified grid itself. The extra memory used consists only of a few integer variables for loop counters and to store temporary values during calculations, and their memory footprint remains constant regardless of the dimensions of the input grid (number of rows and columns). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty matrix input	Return 0 immediately since no submatrices can exist.
Matrix with 0 rows or 0 columns	Return 0 immediately as a matrix is effectively empty.
Matrix with 1 row and 1 column (single element)	Return 1 if the single element is 1, otherwise return 0.
Matrix with all 0s	Return 0 as there are no square submatrices with all 1s.
Matrix with all 1s	Calculate the number of square submatrices by iterating through possible sizes and counts them.
Large matrix dimensions potentially causing integer overflow when counting	Use a larger integer data type (e.g., long) for the count to prevent overflow.
Rectangular matrix (number of rows != number of columns)	The algorithm should correctly handle rectangular matrices by considering the minimum dimension when determining the maximum possible square size.
Matrix with alternating 0s and 1s (checkerboard pattern)	The algorithm should correctly identify and count any valid square submatrices of 1s.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions (rows and columns) constraints for the input matrix? Can the matrix be empty?
Can the input matrix contain values other than 0 and 1?
Could you provide a small example to illustrate the expected output for a given matrix?
If the matrix contains no square submatrices with all 1s, what should the return value be (e.g., 0, null, an error)?
Does the square submatrix have to be contiguous, or can it be formed by selecting elements from different rows and columns?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the smallest possible squares: squares that are just a single square from the grid.
Check if each of these tiny squares contains a 1. If it does, count it.
Now, consider squares of size 2x2. Look at every possible location in the grid where a 2x2 square could fit.
For each possible 2x2 square, check if all four squares inside it contain a 1. If they do, count it.
Repeat this process for larger and larger squares: 3x3, 4x4, and so on, until you reach the maximum possible size of a square that could fit within the original grid.
Each time, you check every possible location for that size square and see if all squares inside contain a 1.
Add up the counts from each square size to get the total number of square submatrices that contain all 1s.

Code Implementation

def count_square_submatrices_brute_force(matrix):
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    total_square_count = 0

    # Iterate through all possible square sizes
    for square_side in range(1, min(rows, cols) + 1):
        # Iterate through the matrix to check each possible top-left corner.
        for row_start in range(rows - square_side + 1):
            for col_start in range(cols - square_side + 1):
                is_all_ones = True

                # Check if the current square has all ones
                for row_index in range(row_start, row_start + square_side):
                    for col_index in range(col_start, col_start + square_side):
                        if matrix[row_index][col_index] == 0:
                            is_all_ones = False
                            break
                    if not is_all_ones:
                        break

                # Increment the count if the square contains all ones
                if is_all_ones:
                    total_square_count += 1

    return total_square_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Look at each number in the grid, one by one.
If the current number is zero, then the largest square that ends here has size zero. We don't need to do anything.
If the current number is one, then the size of the largest square that ends here depends on its three neighbors: the one above, the one to the left, and the one diagonally above and to the left.
Take the smallest of those three neighbors. Add one to that smallest value. This gives the size of the largest square ending at the current number.
Update the current number with this new value (the size of the largest square).
Keep track of the total size of all squares you've found along the way. This is the sum of all the updated values in the grid.
Once you've looked at every number, the total size is the answer: the number of square submatrices with all ones.

Code Implementation

def count_squares(matrix):
    total_square_count = 0
    rows = len(matrix)
    columns = len(matrix[0])

    for row_index in range(rows):
        for column_index in range(columns):
            if matrix[row_index][column_index] == 1:
                # Find min of neighbors to determine square size.
                if row_index > 0 and column_index > 0:

                    matrix[row_index][column_index] = min(
                        matrix[row_index - 1][column_index],
                        matrix[row_index][column_index - 1],
                        matrix[row_index - 1][column_index - 1]
                    ) + 1

                # Add current square size to overall count.
                total_square_count += matrix[row_index][column_index]

    return total_square_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix input	Return 0 immediately since no submatrices can exist.
Matrix with 0 rows or 0 columns	Return 0 immediately as a matrix is effectively empty.
Matrix with 1 row and 1 column (single element)	Return 1 if the single element is 1, otherwise return 0.
Matrix with all 0s	Return 0 as there are no square submatrices with all 1s.
Matrix with all 1s	Calculate the number of square submatrices by iterating through possible sizes and counts them.
Large matrix dimensions potentially causing integer overflow when counting	Use a larger integer data type (e.g., long) for the count to prevent overflow.
Rectangular matrix (number of rows != number of columns)	The algorithm should correctly handle rectangular matrices by considering the minimum dimension when determining the maximum possible square size.
Matrix with alternating 0s and 1s (checkerboard pattern)	The algorithm should correctly identify and count any valid square submatrices of 1s.