# Count Submatrices With Equal Frequency of X and Y **Difficulty:** MEDIUM [External](https://leetcode.com/problems/count-submatrices-with-equal-frequency-of-x-and-y) Canonical: https://scaleengineer.com/dsa/problems/count-submatrices-with-equal-frequency-of-x-and-y **Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum) **Data structures:** Array, Matrix --- ## 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]` * an **equal** frequency of `'X'` and `'Y'`. * **at least** one `'X'`. **Example 1:** **Input:** grid = \[\["X","Y","."\],\["Y",".","."\]\] **Output:** 3 **Explanation:** **![](https://assets.glich.co/dsa/count-submatrices-with-equal-frequency-of-x-and-y/image0.png)** **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 `'.'`. # Approaches ## Brute-Force Iteration This approach involves iterating through every possible submatrix that starts at `(0, 0)`. For each submatrix, we manually count the occurrences of 'X' and 'Y' by iterating through all its cells and then check if the counts satisfy the given conditions. **Time:** O(R² * C²), where R is the number of rows and C is the number of columns. There are four nested loops: two to define the submatrix's bottom-right corner and two to iterate within it. · **Space:** O(1), as we only use a few variables to store counts and loop indices, independent of the grid size. **Pros:** Simple to understand and implement.; Requires no additional space apart from a few counter variables. **Cons:** Extremely inefficient due to the O(R² * C²) time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error on larger grids as specified in the constraints.; Performs a lot of redundant work by re-calculating counts for overlapping submatrices. ### Explanation The problem requires us to count submatrices that start at `(0,0)`. A submatrix is therefore uniquely defined by its bottom-right corner, say at `(r, c)`. The most straightforward way to solve this is to iterate through all possible bottom-right corners. For each `(r, c)` from `(0, 0)` to `(rows-1, cols-1)`, we consider the submatrix formed by the rectangle from `(0, 0)` to `(r, c)`. We then iterate through every cell `(i, j)` within this submatrix (where `0 <= i <= r` and `0 <= j <= c`) to count the number of 'X's and 'Y's. After getting the counts, we check if the number of 'X's is equal to the number of 'Y's and if there is at least one 'X'. If these conditions hold, we increment a counter. This method is simple to conceptualize but computationally expensive because for each submatrix, we recount all its elements, leading to significant overlap in calculations. ```java class Solution { public int numberOfSubmatrices(char[][] grid) { int rows = grid.length; int cols = grid[0].length; int count = 0; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { // For each submatrix ending at (r, c) int xCount = 0; int yCount = 0; // Iterate through the submatrix to count 'X' and 'Y' for (int i = 0; i <= r; i++) { for (int j = 0; j <= c; j++) { if (grid[i][j] == 'X') { xCount++; } else if (grid[i][j] == 'Y') { yCount++; } } } // Check conditions if (xCount > 0 && xCount == yCount) { count++; } } } return count; } } ``` ### Algorithm - 1. Initialize a counter `count` to 0. - 2. Get the dimensions of the grid, `R` (rows) and `C` (columns). - 3. Iterate `r` from `0` to `R-1`. This `r` represents the row index of the bottom-right corner of a submatrix. - 4. Inside the row loop, iterate `c` from `0` to `C-1`. This `c` represents the column index of the bottom-right corner. - 5. For each submatrix defined by top-left `(0, 0)` and bottom-right `(r, c)`, initialize `xCount = 0` and `yCount = 0`. - 6. Start another pair of nested loops to iterate through the cells of this submatrix: `i` from `0` to `r` and `j` from `0` to `c`. - 7. Inside the innermost loops, check `grid[i][j]`. If it's 'X', increment `xCount`. If it's 'Y', increment `yCount`. - 8. After counting is complete for the submatrix, check if the conditions are met: `xCount > 0` and `xCount == yCount`. - 9. If both conditions are true, increment the main `count`. - 10. After all loops complete, return `count`. ## Optimized Counting with 2D Prefix Sums This approach significantly improves performance by pre-calculating the counts of 'X' and 'Y' for all submatrices starting at `(0, 0)`. We use a 2D prefix sum technique, which allows us to find the counts for any such submatrix in O(1) time after an initial O(R*C) preprocessing step. **Time:** O(R * C). Building the prefix sum arrays takes O(R*C) time. Then, iterating through all possible submatrices and checking the conditions takes another O(R*C) time. The total time is linear in the number of cells in the grid. · **Space:** O(R * C) to store the two prefix sum arrays. Each array has a size of (R+1) x (C+1). **Pros:** Highly efficient with a time complexity of O(R*C), which is optimal.; The logic is a standard and powerful technique for 2D range query problems. **Cons:** Requires additional space proportional to the size of the grid, which might be large. ### Explanation The bottleneck in the brute-force approach is the repeated counting. We can eliminate this by pre-calculating the counts. A 2D prefix sum array is a classic technique for this. Since we need counts for both 'X' and 'Y', we will use two prefix sum arrays: `prefixX` and `prefixY`. The array `prefixX[i][j]` will store the total number of 'X's in the rectangular subgrid from `(0, 0)` to `(i-1, j-1)`. Similarly for `prefixY`. These arrays are typically of size `(rows+1) x (cols+1)` to simplify boundary conditions. They can be built in a single pass over the grid using the formula: `prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + value_at_grid[i-1][j-1]` Once these prefix sum arrays are computed, we can find the count of 'X's and 'Y's for any submatrix starting at `(0,0)` and ending at `(r,c)` in O(1) time by simply looking up `prefixX[r+1][c+1]` and `prefixY[r+1][c+1]`. We then iterate through all possible bottom-right corners `(r,c)`, perform this O(1) lookup, check the conditions, and update our count. ```java class Solution { public int numberOfSubmatrices(char[][] grid) { int rows = grid.length; int cols = grid[0].length; int[][] prefixX = new int[rows + 1][cols + 1]; int[][] prefixY = new int[rows + 1][cols + 1]; for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { int isX = (grid[i - 1][j - 1] == 'X') ? 1 : 0; int isY = (grid[i - 1][j - 1] == 'Y') ? 1 : 0; prefixX[i][j] = prefixX[i - 1][j] + prefixX[i][j - 1] - prefixX[i - 1][j - 1] + isX; prefixY[i][j] = prefixY[i - 1][j] + prefixY[i][j - 1] - prefixY[i - 1][j - 1] + isY; } } int count = 0; for (int r = 1; r <= rows; r++) { for (int c = 1; c <= cols; c++) { int xCount = prefixX[r][c]; int yCount = prefixY[r][c]; if (xCount > 0 && xCount == yCount) { count++; } } } return count; } } ``` ### Algorithm - 1. Get the grid dimensions `R` and `C`. - 2. Create two `(R+1) x (C+1)` integer arrays, `prefixX` and `prefixY`, initialized to zeros. `prefixX[i][j]` will store the count of 'X's in the submatrix from `(0,0)` to `(i-1, j-1)`. - 3. Populate the prefix sum arrays by iterating `i` from `1` to `R` and `j` from `1` to `C`. - 4. Use the recurrence relation: `prefixX[i][j] = prefixX[i-1][j] + prefixX[i][j-1] - prefixX[i-1][j-1] + (grid[i-1][j-1] == 'X' ? 1 : 0)`. Do the same for `prefixY`. - 5. Initialize a result `count = 0`. - 6. Iterate through all possible bottom-right corners of the submatrices. Let the corner be at `(r, c)` in the original grid, which corresponds to `(r+1, c+1)` in the prefix sum arrays. - 7. For each corner `(r, c)`, the count of 'X's is `prefixX[r+1][c+1]` and 'Y's is `prefixY[r+1][c+1]`. - 8. Check if `prefixX[r+1][c+1] > 0` and `prefixX[r+1][c+1] == prefixY[r+1][c+1]`. - 9. If the conditions are met, increment `count`. - 10. Return `count`. ## Space-Optimized 2D Prefix Sum This approach is a space-optimized version of the 2D prefix sum method. By observing that the calculation of prefix sums for the current row only depends on the prefix sums of the previous row, we can reduce the space complexity from O(R*C) to O(C) while maintaining the optimal O(R*C) time complexity. **Time:** O(R * C). We iterate through each cell of the grid exactly once, performing constant time operations at each cell. · **Space:** O(C), where C is the number of columns. We only need two arrays of size C to store the column-wise prefix sums. **Pros:** Optimal time complexity, same as the standard 2D prefix sum approach.; Improved space complexity, making it more memory-efficient for grids with a large number of rows. **Cons:** The logic can be slightly less intuitive to grasp compared to the full 2D prefix sum approach. ### Explanation While the 2D prefix sum approach is time-efficient, its space usage can be improved. We can process the grid row by row. Instead of a full 2D array, we only need to maintain the prefix sums for each column up to the current row being processed. We use two 1D arrays, `colPrefixX` and `colPrefixY`, of size `C`. `colPrefixX[c]` will store the total count of 'X's in column `c` from row `0` down to the current row `r`. We iterate through the grid row by row. For each row `r`, we first update the `colPrefixX` and `colPrefixY` arrays based on the characters in `grid[r]`. Then, for the current row `r`, we can calculate the total counts for any submatrix ending at `(r, c)`. The total count of 'X's in the submatrix from `(0,0)` to `(r,c)` is the sum of `colPrefixX[j]` for `j` from `0` to `c`. We can compute this sum efficiently by maintaining a running sum (`currentX` and `currentY`) as we iterate through the columns of the current row. At each cell `(r, c)`, these running sums give us the total counts for the submatrix ending at that cell, allowing us to check the conditions. ```java class Solution { public int numberOfSubmatrices(char[][] grid) { int rows = grid.length; int cols = grid[0].length; int count = 0; // colPrefixX[c] stores the count of 'X' in column c from row 0 to the current row int[] colPrefixX = new int[cols]; int[] colPrefixY = new int[cols]; for (int r = 0; r < rows; r++) { int currentX = 0; // Running sum of X's for submatrix ending at (r, c) int currentY = 0; // Running sum of Y's for submatrix ending at (r, c) for (int c = 0; c < cols; c++) { // Update column-wise prefix sums for the current row if (grid[r][c] == 'X') { colPrefixX[c]++; } else if (grid[r][c] == 'Y') { colPrefixY[c]++; } // Update the total counts for the submatrix (0,0) to (r,c) currentX += colPrefixX[c]; currentY += colPrefixY[c]; // Check conditions if (currentX > 0 && currentX == currentY) { count++; } } } return count; } } ``` ### Algorithm - 1. Get grid dimensions `R` and `C`. - 2. Create two 1D arrays of size `C`, `colPrefixX` and `colPrefixY`, initialized to zeros. These will store column-wise prefix sums up to the current row. - 3. Initialize `count = 0`. - 4. Iterate through each row `r` from `0` to `R-1`. - 5. For each row, initialize `currentX = 0` and `currentY = 0`. These will act as running prefix sums across columns for the current row. - 6. Iterate through each column `c` from `0` to `C-1`. - 7. Update the column-wise prefix sums: `colPrefixX[c]` and `colPrefixY[c]` are incremented if `grid[r][c]` is 'X' or 'Y' respectively. - 8. Update the running prefix sums for the submatrix ending at `(r, c)`: `currentX += colPrefixX[c]` and `currentY += colPrefixY[c]`. - 9. The variables `currentX` and `currentY` now hold the total counts for the submatrix from `(0,0)` to `(r,c)`. - 10. Check the conditions: if `currentX > 0` and `currentX == currentY`, increment `count`. - 11. After iterating through all rows and columns, return `count`. # Solutions ### Java ```java 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; } } ``` ### CPP ```cpp class Solution { public: int numberOfSubmatrices(vector> &grid) { int m = grid.size(), n = grid[0].size(); vector>> s(m + 1, vector>(n + 1, vector(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; } }; ``` ### Python ```python 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 ```