Count Submatrices With Equal Frequency of X and Y

Count Submatrices With Equal Frequency of X and Y - Problem

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] (top-left corner)
An equal frequency of 'X' and 'Y'
At least one 'X'

A submatrix is defined by its top-left corner at (0, 0) and bottom-right corner at (i, j) where 0 ≤ i < m and 0 ≤ j < n.

Input & Output

Example 1 — Basic Case

$ Input: grid = [["X","Y","."],[".","Y","X"]]

› Output: 3

💡 Note: Valid submatrices: (0,0) to (0,1) has X=1,Y=1; (0,0) to (1,2) has X=2,Y=2; (0,0) to (1,1) has X=1,Y=2 (invalid)

Example 2 — Single Cell

$ Input: grid = [["X"]]

› Output: 0

💡 Note: Only submatrix is (0,0) to (0,0) with X=1,Y=0. Not equal counts, so 0 valid submatrices

Example 3 — No X Characters

$ Input: grid = [["Y",".","Y"]]

› Output: 0

💡 Note: No submatrix contains at least one X, so result is 0

Constraints

1 ≤ grid.length, grid[i].length ≤ 100
grid[i][j] is either 'X', 'Y', or '.'

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D matrix with X, Y, and dot characters

Check Submatrices

All submatrices from (0,0) to various endpoints

Count Valid

Those with equal X,Y counts and at least one X

Key Takeaway

🎯 Key Insight: Use prefix sums to calculate submatrix character counts in O(1) time instead of O(mn) repeated counting

Asked in

G Google 25 M Microsoft 18 A Amazon 15

The key insight is to use 2D prefix sums to avoid repeatedly counting characters in overlapping submatrices. We build prefix sum arrays for X and Y counts, then check each submatrix from (0,0) to (i,j) in O(1) time. Best approach uses prefix sums with Time: O(mn), Space: O(mn).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(m²n²)	O(1)	Check every submatrix by counting X, Y, and dots from scratch
Prefix Sum Optimization	O(mn)	O(mn)	Use 2D prefix sums to count characters in any submatrix in O(1) time

Brute Force — Algorithm Steps

Iterate through all possible bottom-right corners
For each submatrix, count X's and Y's from scratch
Check if count_X == count_Y and count_X > 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Bottom-Right

Choose bottom-right corner (i,j)

Count Characters

Count all X's and Y's in submatrix

Check Condition

Verify equal count and at least one X

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char** grid, int m, int n) {
    int count = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int xCount = 0;
            int yCount = 0;
            
            // Count X's and Y's in submatrix from (0,0) to (i,j)
            for (int r = 0; r <= i; r++) {
                for (int c = 0; c <= j; c++) {
                    if (grid[r][c] == 'X') {
                        xCount++;
                    } else if (grid[r][c] == 'Y') {
                        yCount++;
                    }
                }
            }
            
            // Check if equal frequency and at least one X
            if (xCount == yCount && xCount > 0) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small test cases
    char** grid = (char**)malloc(10 * sizeof(char*));
    int m = 0, n = 0;
    
    // Parse manually - simplified for basic cases
    char* token = strtok(line, "[],\"");
    while (token != NULL && m < 10) {
        if (strlen(token) == 1 && (token[0] == 'X' || token[0] == 'Y' || token[0] == '.')) {
            if (n == 0) {
                grid[m] = (char*)malloc(10 * sizeof(char));
            }
            grid[m][n] = token[0];
            n++;
        }
        token = strtok(NULL, "[],\"");
    }
    m = 1; // Simplified for demo
    
    printf("%d\n", solution(grid, m, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²)

Nested loops for bottom-right corner (m×n) and inner loops to count each submatrix (m×n)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to store counts, no extra data structures

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler