Skip to content

3212. Count Submatrices With Equal Frequency of X and Y

SourceWeekly Contest 405 Q3DifficultyMediumRating1672

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

Thinking

Every counted submatrix must include the top-left cell \((0,0)\), so there are only \(O(mn)\) candidates, with \(m,n\le 10^3\). Rescanning each submatrix would be cubic and too slow.

A 2D prefix sum answers the X/Y counts of \([0,0]\)–\((i,j)\) in \(O(1)\). At each cell, update by inclusion–exclusion and count when the X count is positive and equals the Y count. One \(O(mn)\) pass suffices.

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;
}

 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
28
impl Solution {
    pub fn number_of_submatrices(grid: Vec<Vec<char>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut s = vec![vec![vec![0i32; 2]; n + 1]; m + 1];
        let mut ans = 0;

        for i in 1..=m {
            for j in 1..=n {
                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' { 1 } else { 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' { 1 } else { 0 };

                if s[i][j][0] > 0 && s[i][j][0] == s[i][j][1] {
                    ans += 1;
                }
            }
        }

        ans
    }
}

Comments