Count Submatrices With Equal Frequency of X and Y

Problem Description

Ah, the classic dilemma of counting submatrices with equal frequencies of ‘X’ and ‘Y’. It’s like trying to find balance in a relationship where one partner loves pizza and the other is a salad enthusiast. You know, the struggle is real!

In this problem, you are given a binary grid filled with ‘X’ and ‘Y’. Your task is to count all the submatrices (rectangular sections of the grid) that contain an equal number of ‘X’s and ‘Y’s. Imagine you’re at a party, and you want to find the perfect group of friends who are equally divided between pizza lovers and salad enthusiasts.

Example

Consider the following grid:


X Y X
Y X Y
X Y X

In this case, there are several submatrices that have equal counts of ‘X’ and ‘Y’. Your job is to find and count them all.

Solution

Before we dive into the code, let’s take a moment to appreciate the beauty of programming. Here’s the Python solution to the problem:


class Solution:
    def numberOfSubmatrices(self, grid: list[list[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        ans = 0
        # x[i][j] := the number of 'X' in grid[0..i)[0..j)
        x = [[0] * (n + 1) for _ in range(m + 1)]
        # y[i][j] := the number of 'Y' in grid[0..i)[0..j)
        y = [[0] * (n + 1) for _ in range(m + 1)]

        for i, row in enumerate(grid):
            for j, cell in enumerate(row):
                x[i + 1][j + 1] = (cell == 'X') + x[i][j + 1] + x[i + 1][j] - x[i][j]
                y[i + 1][j + 1] = (cell == 'Y') + y[i][j + 1] + y[i + 1][j] - y[i][j]
                if x[i + 1][j + 1] > 0 and x[i + 1][j + 1] == y[i + 1][j + 1]:
                    ans += 1

        return ans

Approach Explanation

The approach taken in the code is quite elegant. It utilizes a prefix sum technique to keep track of the counts of ‘X’ and ‘Y’ in the grid. By iterating through each cell, it builds two matrices: one for ‘X’ counts and another for ‘Y’ counts. Whenever it finds a submatrix where the counts of ‘X’ and ‘Y’ are equal, it increments the answer.

Time and Space Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid. This is because we are iterating through each cell in the grid.
Space Complexity: O(m * n) as well, due to the additional matrices used to store the counts of ‘X’ and ‘Y’.

Real-World Example

Imagine you are organizing a potluck dinner. You want to ensure that there are equal numbers of pizza and salad lovers in each table group. You can think of the grid as your seating arrangement, and the submatrices as the different table groups. Your goal is to find all possible table arrangements where the number of pizza lovers equals the number of salad lovers.