Skip to content

3212. Count Submatrices With Equal Frequency of X and Y

Description

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 '.'.

Solutions

Solution 1: 2D Prefix Sum

According to the problem description, we only need to calculate the prefix sums $s[i][j][0]$ and $s[i][j][1]$ for each position $(i, j)$, which represent the number of characters X and Y in the submatrix from $(0, 0)$ to $(i, j)$, respectively. If $s[i][j][0] > 0$ and $s[i][j][0] = s[i][j][1]$, it means the condition is met, and we increment the answer by one.

After traversing all positions, return the answer.

The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Here, $m$ and $n$ represent the number of rows and columns of the matrix, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        s = [[[0] * 2 for _ in range(n + 1)] for _ in range(m + 1)]
        ans = 0
        for i, row in enumerate(grid, 1):
            for j, x in enumerate(row, 1):
                s[i][j][0] = s[i - 1][j][0] + s[i][j - 1][0] - s[i - 1][j - 1][0]
                s[i][j][1] = s[i - 1][j][1] + s[i][j - 1][1] - s[i - 1][j - 1][1]
                if x != ".":
                    s[i][j][ord(x) & 1] += 1
                if s[i][j][0] > 0 and s[i][j][0] == s[i][j][1]:
                    ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numberOfSubmatrices(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][][] s = new int[m + 1][n + 1][2];
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                s[i][j][0] = s[i - 1][j][0] + s[i][j - 1][0] - s[i - 1][j - 1][0]
                    + (grid[i - 1][j - 1] == 'X' ? 1 : 0);
                s[i][j][1] = s[i - 1][j][1] + s[i][j - 1][1] - s[i - 1][j - 1][1]
                    + (grid[i - 1][j - 1] == 'Y' ? 1 : 0);
                if (s[i][j][0] > 0 && s[i][j][0] == s[i][j][1]) {
                    ++ans;
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numberOfSubmatrices(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<vector<int>>> s(m + 1, vector<vector<int>>(n + 1, vector<int>(2)));
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                s[i][j][0] = s[i - 1][j][0] + s[i][j - 1][0] - s[i - 1][j - 1][0]
                    + (grid[i - 1][j - 1] == 'X' ? 1 : 0);
                s[i][j][1] = s[i - 1][j][1] + s[i][j - 1][1] - s[i - 1][j - 1][1]
                    + (grid[i - 1][j - 1] == 'Y' ? 1 : 0);
                if (s[i][j][0] > 0 && s[i][j][0] == s[i][j][1]) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func numberOfSubmatrices(grid [][]byte) (ans int) {
    m, n := len(grid), len(grid[0])
    s := make([][][]int, m+1)
    for i := range s {
        s[i] = make([][]int, n+1)
        for j := range s[i] {
            s[i][j] = make([]int, 2)
        }
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            s[i][j][0] = s[i-1][j][0] + s[i][j-1][0] - s[i-1][j-1][0]
            if grid[i-1][j-1] == 'X' {
                s[i][j][0]++
            }
            s[i][j][1] = s[i-1][j][1] + s[i][j-1][1] - s[i-1][j-1][1]
            if grid[i-1][j-1] == 'Y' {
                s[i][j][1]++
            }
            if s[i][j][0] > 0 && s[i][j][0] == s[i][j][1] {
                ans++
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function numberOfSubmatrices(grid: string[][]): number {
    const [m, n] = [grid.length, grid[0].length];
    const s = Array.from({ length: m + 1 }, () => Array.from({ length: n + 1 }, () => [0, 0]));
    let ans = 0;

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

    return ans;
}

Comments