Count Submatrices With Equal Frequency of X and Y

Ah, the classic problem of counting submatrices with equal frequencies of ‘X’ and ‘Y’. It’s like trying to find a balance in a relationship where one partner loves pizza and the other is obsessed with salad. You know, the struggle is real! In this problem, we are tasked with finding all the submatrices in a given grid that contain an equal number of ‘X’s and ‘Y’s. Sounds simple, right? Well, buckle up, because it’s not as easy as it sounds!

Imagine you’re at a party, and you’re trying to count how many people are wearing red and how many are wearing blue. If you find a group where the numbers are equal, you’ve got yourself a submatrix! But instead of people, we have characters in a grid.

Language Options

Code Solution


class Solution {
  public int numberOfSubmatrices(char[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    int ans = 0;
    int[][] x = new int[m + 1][n + 1];
    int[][] y = new int[m + 1][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 Explanation

The code uses a dynamic programming approach to count the number of ‘X’s and ‘Y’s in the grid. It maintains two 2D arrays, x and y, which store the cumulative counts of ‘X’s and ‘Y’s respectively. As we iterate through the grid, we update these counts and check if they are equal. If they are, we increment our answer.

Time and Space Complexity

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

Real-World Example

Think of a scenario where you are organizing a sports event. You have two teams, Team X and Team Y. You want to ensure that in every match (submatrix), both teams have an equal number of players. If you can find such matches, you can declare them as fair games! This problem is essentially about finding those fair games in a grid of players.