Daily LeetCode - by Vítor Belim

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

This code counts the number of submatrices in a grid where the count of 'X' characters equals the count of 'Y' characters. It uses dynamic programming with a 2D array dp where each cell stores a pair [countX, countY] representing the cumulative counts of 'X' and 'Y' from the top-left corner to that cell (a 2D prefix sum). For each position, it combines values from the top, left, and diagonal neighbors using the inclusion-exclusion principle to avoid double-counting, then adds 1 (for 'X') or 1 (for 'Y') if the current cell contains that character. Finally, whenever the counts become equal and positive (dp[row][col][0] > 0 && dp[row][col][0] === dp[row][col][1]), it means at least one valid submatrix ending at that position has balanced 'X' and 'Y' characters, so the result counter increments.

Language: javascript(2026-03-19 09:03)DONE

CPU Performance8.70%

Memory Performance13.04%

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numberOfSubmatrices = function(grid) {
    const m = grid.length;
    const n = grid[0].length;

    const dp = Array.from({ length: m }, () => Array.from({ length: n }, () => [0, 0]));
    let res = 0;

    for (let row = 0; row < m; row++) {
        for (let col = 0; col < n; col++) {
            const top = row > 0 ? dp[row - 1][col] : [0, 0];
            const left = col > 0 ? dp[row][col - 1] : [0, 0];
            const diag = row > 0 && col > 0 ? dp[row - 1][col - 1] : [0, 0];

            const dx = grid[row][col] === 'X' ? 1 : 0;
            const dy = grid[row][col] === 'Y' ? 1 : 0;

            dp[row][col] = [
                dp[row][col][0] + dx + top[0] + left[0] - diag[0],
                dp[row][col][1] + dy + top[1] + left[1] - diag[1],
            ]

            if (dp[row][col][0] > 0 && dp[row][col][0] === dp[row][col][1]) {
                res++;
            }
        }
    }

    return res;
};

Description

Solutions

AI Explanation