Count Submatrices With Equal Frequency of X and Y

Explore Other Solutions

Problem Description

Ah, the classic dilemma of counting submatrices with equal frequencies of ‘X’ and ‘Y’. Imagine you’re at a party, and you notice that there are exactly as many people wearing X-themed shirts as there are wearing Y-themed shirts. You’d want to count how many groups of friends (submatrices) are standing together, right? Well, this problem is just like that, but with a grid of characters instead of party-goers.

In this problem, you’re given a 2D grid filled with ‘X’ and ‘Y’. Your task is to count all the submatrices (rectangular sections of the grid) where the number of ‘X’s is equal to the number of ‘Y’s. Sounds simple? Well, it’s like trying to find a needle in a haystack, except the haystack is a grid, and the needle is a perfectly balanced submatrix!

Code Solution


class Solution {
 public:
  int numberOfSubmatrices(vector>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    int ans = 0;
    vector> x(m + 1, vector(n + 1));
    vector> y(m + 1, vector(n + 1));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        x[i + 1][j + 1] =
            (grid[i][j] == 'X' ? 1 : 0) + x[i][j + 1] + x[i + 1][j] - x[i][j];
        y[i + 1][j + 1] =
            (grid[i][j] == 'Y' ? 1 : 0) + y[i][j + 1] + y[i + 1][j] - y[i][j];
        if (x[i + 1][j + 1] > 0 && x[i + 1][j + 1] == y[i + 1][j + 1])
          ++ans;
      }

    return ans;
  }
};

Approach

The approach taken in this solution involves creating two prefix sum matrices: one for counting ‘X’s and another for counting ‘Y’s. As we iterate through the grid, we update these matrices to keep track of the cumulative counts of ‘X’ and ‘Y’ up to each point. Whenever we find a submatrix where the counts of ‘X’ and ‘Y’ are equal, we increment our answer. This method efficiently counts the valid submatrices without needing to check each one individually.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(m * n)
Space Complexity	O(m * n)

Real-World Example

Imagine you’re at a picnic, and you have a basket filled with apples (X) and oranges (Y). You want to find all the combinations of fruits in your basket that have an equal number of apples and oranges. This problem is just like that, but instead of fruits, we have characters in a grid. The solution helps you find all the possible combinations (submatrices) where the number of apples equals the number of oranges!