Jobs

Interviews

Discussions

Count Submatrices With Equal Frequency of X and Y

#282 Most AskedMedium

Count Submatrices With Equal Frequency of X and Y #282 Most Asked

Medium

Microsoft

12 views

Topics:

Arrays

Given a 2D character matrix grid, where grid[i][j] is either 'X', 'Y', or '.', return the number of submatrices that contain:

grid[0][0]
an equal frequency of 'X' and 'Y'.
at least one 'X'.

Example 1:

Input: grid = [["X","Y","."],["Y",".","."]]

Output: 3

Explanation:

Example 2:

Input: grid = [["X","X"],["X","Y"]]

Output: 0

Explanation:

No submatrix has an equal frequency of 'X' and 'Y'.

Example 3:

Input: grid = [[".","."],[".","."]]

Output: 0

Explanation:

No submatrix has at least one 'X'.

Constraints:

1 <= grid.length, grid[i].length <= 1000
grid[i][j] is either 'X', 'Y', or '.'.

Try coding it in LeetCode

Count Submatrices With Equal Frequency of X and Y

#282 Most AskedMedium

Count Submatrices With Equal Frequency of X and Y #282 Most Asked

Medium

Microsoft

12 views

Topics:

Arrays

Given a 2D character matrix grid, where grid[i][j] is either 'X', 'Y', or '.', return the number of submatrices that contain:

grid[0][0]
an equal frequency of 'X' and 'Y'.
at least one 'X'.

Example 1:

Input: grid = [["X","Y","."],["Y",".","."]]

Output: 3

Explanation:

Example 2:

Input: grid = [["X","X"],["X","Y"]]

Output: 0

Explanation:

No submatrix has an equal frequency of 'X' and 'Y'.

Example 3:

Input: grid = [[".","."],[".","."]]

Output: 0

Explanation:

No submatrix has at least one 'X'.

Constraints:

1 <= grid.length, grid[i].length <= 1000
grid[i][j] is either 'X', 'Y', or '.'.

Try coding it in LeetCode

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 constraints on the dimensions of the matrix, and the ranges for x, y, and the matrix elements?
If x and y are the same value, is a submatrix with an equal number of them considered a valid submatrix?
If no submatrices satisfy the condition, what value should I return?
Can the input matrix be empty or null? What about x or y being null?
Is the matrix guaranteed to be rectangular (i.e., all rows have the same length)?

Brute Force Solution

Approach

The brute force strategy involves checking every possible submatrix within the given matrix. For each submatrix, we count the occurrences of X and Y and determine if they are equal. If they are equal, we increment our count of valid submatrices.

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

Consider every possible top-left corner of a submatrix within the bigger matrix.
For each top-left corner, consider every possible bottom-right corner that is located below and to the right of it, thus defining a submatrix.
Within each defined submatrix, count how many times X appears and how many times Y appears.
Compare the counts of X and Y. If they are equal, then this submatrix is a valid one, so add 1 to our total count.
Repeat steps 2-4 until you have explored every possible submatrix, determined by all combinations of top-left and bottom-right corners.
Once all submatrices have been examined, the final total count represents the number of valid submatrices with an equal frequency of X and Y.

Code Implementation

def count_submatrices_equal_frequency(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    count = 0

    for top_row in range(rows):
        for left_col in range(cols):

            # Iterate through all possible bottom right corners
            for bottom_row in range(top_row, rows):
                for right_col in range(left_col, cols):
                    x_count = 0
                    y_count = 0

                    # Count X's and Y's within the submatrix
                    for i in range(top_row, bottom_row + 1):
                        for j in range(left_col, right_col + 1):
                            if matrix[i][j] == 'X':
                                x_count += 1
                            elif matrix[i][j] == 'Y':
                                y_count += 1

                    # Check if the counts are equal
                    # If they are, increment our counter
                    if x_count == y_count:
                        count += 1

    return count

Big(O) Analysis

Time Complexity

O(m^3 * n^3) – The brute force approach iterates through all possible top-left corners, which is O(m * n) where m is the number of rows and n is the number of columns. For each top-left corner, it iterates through all possible bottom-right corners, which is also O(m * n) in the worst case. For each submatrix defined by these corners, we then need to count the occurrences of X and Y, which takes O(m * n) time in the worst case. Therefore, the overall time complexity is O(m * n) * O(m * n) * O(m * n), which simplifies to O(m^3 * n^3).

Space Complexity

O(1) – The brute force approach, as described, iterates through all possible submatrices by considering every possible top-left and bottom-right corner. Within each submatrix, it counts the occurrences of X and Y using constant space variables. The algorithm does not employ any auxiliary data structures that scale with the input matrix size, therefore only a fixed amount of extra memory is used regardless of the dimensions of the input matrix. The only extra space is used for storing the X and Y counts, which are independent of the input size N (number of elements in the matrix). Thus the space complexity is constant.

Optimal Solution

Approach

The key is to efficiently count submatrices that meet the criteria without checking every single possible submatrix. We use a technique to precompute sums, allowing us to quickly determine the count of X's and Y's within any rectangular region.

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

First, create a helper structure that lets you quickly calculate the sum of any rectangular portion of the original matrix. This structure records cumulative counts from the start up to each point in the matrix.
Pick two corners of the original matrix to define a submatrix. Instead of manually counting X's and Y's in that submatrix, use the helper structure to determine the total number of X's and Y's very quickly.
Check if the number of X's equals the number of Y's. If they are equal, increment a counter.
Repeat the corner selection and counting process for all possible submatrices within the original matrix.
The final count you've accumulated is the total number of submatrices with an equal frequency of X and Y.

Code Implementation

def count_submatrices(matrix, x_value, y_value):
    rows = len(matrix)
    cols = len(matrix[0])

    # Initialize the difference table with zeros.
    difference_table = [[0] * (cols + 1) for _ in range(rows + 1)]

    # Populate the difference table.
    for row_index in range(1, rows + 1):
        for col_index in range(1, cols + 1):
            if matrix[row_index-1][col_index-1] == x_value:
                difference_table[row_index][col_index] = difference_table[row_index - 1][col_index] + difference_table[row_index][col_index - 1] - difference_table[row_index - 1][col_index - 1] + 1
            elif matrix[row_index-1][col_index-1] == y_value:
                difference_table[row_index][col_index] = difference_table[row_index - 1][col_index] + difference_table[row_index][col_index - 1] - difference_table[row_index - 1][col_index - 1] - 1
            else:
                difference_table[row_index][col_index] = difference_table[row_index - 1][col_index] + difference_table[row_index][col_index - 1] - difference_table[row_index - 1][col_index - 1]

    equal_frequency_count = 0

    # Iterate through all possible submatrices.
    for row_start in range(1, rows + 1):
        for col_start in range(1, cols + 1):
            for row_end in range(row_start, rows + 1):
                for col_end in range(col_start, cols + 1):

                    # Calculate the difference of X and Y counts in the submatrix.
                    submatrix_difference = difference_table[row_end][col_end] - difference_table[row_start - 1][col_end] - difference_table[row_end][col_start - 1] + difference_table[row_start - 1][col_start - 1]

                    # Count submatrices with equal frequency.
                    if submatrix_difference == 0:
                        equal_frequency_count += 1

    return equal_frequency_count

Big(O) Analysis

Time Complexity

O(n^4) – The algorithm iterates through all possible submatrices within the original matrix. This involves selecting two corners to define each submatrix. The nested loops to select the top-left corner have O(n^2) complexity, and the nested loops to select the bottom-right corner also have O(n^2) complexity, where n represents the dimensions of the matrix. Inside these loops, a constant-time operation (using the precomputed sums) checks if the number of X's equals the number of Y's. Therefore, the overall time complexity is O(n^2) * O(n^2) which simplifies to O(n^4).

Space Complexity

O(N*M) – The described solution uses a helper structure to store cumulative counts. This structure will be the same size as the original matrix, which has dimensions N rows and M columns, where N is the number of rows and M is the number of columns in the input matrix. Thus, the auxiliary space required for this cumulative count structure is directly proportional to the size of the input matrix (N*M). All other variables used have constant space and do not affect the asymptotic space complexity.

Edge Cases

Case	How to Handle
Null or empty matrix	Return 0, as there are no submatrices to evaluate.
Matrix with zero rows or zero columns	Return 0, as there are no valid submatrices.
Matrix with a single element (1x1 matrix)	Check if the single element is equal to both x and y; if so, return 1, otherwise return 0.
Matrix with all elements equal to x, and y is different	Count submatrices with number of x's and y's both 0, so the return value should be a count of all possible submatrices.
Matrix with all elements equal to y, and x is different	Count submatrices with number of x's and y's both 0, so the return value should be a count of all possible submatrices.
Large matrix (performance considerations)	Use a prefix sum approach to efficiently calculate the frequencies of x and y within submatrices.
x and y are equal	If x and y are equal, we need to find submatrices with an even number of occurrences of x (or y).
Integer overflow when calculating submatrix size	Use `long` data type for calculations involving the product of row and column sizes to prevent overflow.

Null or empty matrix

How to Handle:

Return 0, as there are no submatrices to evaluate.

Matrix with zero rows or zero columns

How to Handle:

Return 0, as there are no valid submatrices.

Matrix with a single element (1x1 matrix)

How to Handle:

Check if the single element is equal to both x and y; if so, return 1, otherwise return 0.

Matrix with all elements equal to x, and y is different

How to Handle:

Count submatrices with number of x's and y's both 0, so the return value should be a count of all possible submatrices.

Matrix with all elements equal to y, and x is different

How to Handle:

Count submatrices with number of x's and y's both 0, so the return value should be a count of all possible submatrices.

Large matrix (performance considerations)

How to Handle:

Use a prefix sum approach to efficiently calculate the frequencies of x and y within submatrices.

x and y are equal

How to Handle:

If x and y are equal, we need to find submatrices with an even number of occurrences of x (or y).

Integer overflow when calculating submatrix size

How to Handle:

Use `long` data type for calculations involving the product of row and column sizes to prevent overflow.

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 constraints on the dimensions of the matrix, and the ranges for x, y, and the matrix elements?
If x and y are the same value, is a submatrix with an equal number of them considered a valid submatrix?
If no submatrices satisfy the condition, what value should I return?
Can the input matrix be empty or null? What about x or y being null?
Is the matrix guaranteed to be rectangular (i.e., all rows have the same length)?

Brute Force Solution

Approach

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

Consider every possible top-left corner of a submatrix within the bigger matrix.
For each top-left corner, consider every possible bottom-right corner that is located below and to the right of it, thus defining a submatrix.
Within each defined submatrix, count how many times X appears and how many times Y appears.
Compare the counts of X and Y. If they are equal, then this submatrix is a valid one, so add 1 to our total count.
Repeat steps 2-4 until you have explored every possible submatrix, determined by all combinations of top-left and bottom-right corners.
Once all submatrices have been examined, the final total count represents the number of valid submatrices with an equal frequency of X and Y.

Code Implementation

def count_submatrices_equal_frequency(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    count = 0

    for top_row in range(rows):
        for left_col in range(cols):

            # Iterate through all possible bottom right corners
            for bottom_row in range(top_row, rows):
                for right_col in range(left_col, cols):
                    x_count = 0
                    y_count = 0

                    # Count X's and Y's within the submatrix
                    for i in range(top_row, bottom_row + 1):
                        for j in range(left_col, right_col + 1):
                            if matrix[i][j] == 'X':
                                x_count += 1
                            elif matrix[i][j] == 'Y':
                                y_count += 1

                    # Check if the counts are equal
                    # If they are, increment our counter
                    if x_count == y_count:
                        count += 1

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, create a helper structure that lets you quickly calculate the sum of any rectangular portion of the original matrix. This structure records cumulative counts from the start up to each point in the matrix.
Pick two corners of the original matrix to define a submatrix. Instead of manually counting X's and Y's in that submatrix, use the helper structure to determine the total number of X's and Y's very quickly.
Check if the number of X's equals the number of Y's. If they are equal, increment a counter.
Repeat the corner selection and counting process for all possible submatrices within the original matrix.
The final count you've accumulated is the total number of submatrices with an equal frequency of X and Y.

Code Implementation

def count_submatrices(matrix, x_value, y_value):
    rows = len(matrix)
    cols = len(matrix[0])

    # Initialize the difference table with zeros.
    difference_table = [[0] * (cols + 1) for _ in range(rows + 1)]

    # Populate the difference table.
    for row_index in range(1, rows + 1):
        for col_index in range(1, cols + 1):
            if matrix[row_index-1][col_index-1] == x_value:
                difference_table[row_index][col_index] = difference_table[row_index - 1][col_index] + difference_table[row_index][col_index - 1] - difference_table[row_index - 1][col_index - 1] + 1
            elif matrix[row_index-1][col_index-1] == y_value:
                difference_table[row_index][col_index] = difference_table[row_index - 1][col_index] + difference_table[row_index][col_index - 1] - difference_table[row_index - 1][col_index - 1] - 1
            else:
                difference_table[row_index][col_index] = difference_table[row_index - 1][col_index] + difference_table[row_index][col_index - 1] - difference_table[row_index - 1][col_index - 1]

    equal_frequency_count = 0

    # Iterate through all possible submatrices.
    for row_start in range(1, rows + 1):
        for col_start in range(1, cols + 1):
            for row_end in range(row_start, rows + 1):
                for col_end in range(col_start, cols + 1):

                    # Calculate the difference of X and Y counts in the submatrix.
                    submatrix_difference = difference_table[row_end][col_end] - difference_table[row_start - 1][col_end] - difference_table[row_end][col_start - 1] + difference_table[row_start - 1][col_start - 1]

                    # Count submatrices with equal frequency.
                    if submatrix_difference == 0:
                        equal_frequency_count += 1

    return equal_frequency_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix	Return 0, as there are no submatrices to evaluate.
Matrix with zero rows or zero columns	Return 0, as there are no valid submatrices.
Matrix with a single element (1x1 matrix)	Check if the single element is equal to both x and y; if so, return 1, otherwise return 0.
Matrix with all elements equal to x, and y is different	Count submatrices with number of x's and y's both 0, so the return value should be a count of all possible submatrices.
Matrix with all elements equal to y, and x is different	Count submatrices with number of x's and y's both 0, so the return value should be a count of all possible submatrices.
Large matrix (performance considerations)	Use a prefix sum approach to efficiently calculate the frequencies of x and y within submatrices.
x and y are equal	If x and y are equal, we need to find submatrices with an even number of occurrences of x (or y).
Integer overflow when calculating submatrix size	Use `long` data type for calculations involving the product of row and column sizes to prevent overflow.

Null or empty matrix

How to Handle:

Return 0, as there are no submatrices to evaluate.

Matrix with zero rows or zero columns

How to Handle:

Return 0, as there are no valid submatrices.

Matrix with a single element (1x1 matrix)

How to Handle:

Check if the single element is equal to both x and y; if so, return 1, otherwise return 0.

Matrix with all elements equal to x, and y is different

How to Handle:

Count submatrices with number of x's and y's both 0, so the return value should be a count of all possible submatrices.

Matrix with all elements equal to y, and x is different

How to Handle:

Count submatrices with number of x's and y's both 0, so the return value should be a count of all possible submatrices.

Large matrix (performance considerations)

How to Handle:

Use a prefix sum approach to efficiently calculate the frequencies of x and y within submatrices.

x and y are equal

How to Handle:

If x and y are equal, we need to find submatrices with an even number of occurrences of x (or y).

Integer overflow when calculating submatrix size

How to Handle:

Use `long` data type for calculations involving the product of row and column sizes to prevent overflow.

0/1114 Microsoft questions completed

0/1114 completed