#2853Time: 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.
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 '.'.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
Initialize a counter count to 0.
Get the dimensions of the grid, R (rows) and C (columns).
Iterate r from 0 to R-1. This r represents the row index of the bottom-right corner of a submatrix.
Inside the row loop, iterate c from 0 to C-1. This c represents the column index of the bottom-right corner.
For each submatrix defined by top-left (0, 0) and bottom-right (r, c), initialize xCount = 0 and yCount = 0.
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.
Inside the innermost loops, check grid[i][j]. If it's 'X', increment xCount. If it's 'Y', increment yCount.
After counting is complete for the submatrix, check if the conditions are met: xCount > 0 and xCount == yCount.
If both conditions are true, increment the main count.
After all loops complete, return count.
Walkthrough
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.
1class Solution {2 public int numberOfSubmatrices(char[][] grid) {3 int rows = grid.length;4 int cols = grid[0].length;5 int count = 0;67 for (int r = 0; r < rows; r++) {8 for (int c = 0; c < cols; c++) {9 // For each submatrix ending at (r, c)10 int xCount = 0;11 int yCount = 0;1213 // Iterate through the submatrix to count 'X' and 'Y'14 for (int i = 0; i <= r; i++) {15 for (int j = 0; j <= c; j++) {16 if (grid[i][j] == 'X') {17 xCount++;18 } else if (grid[i][j] == 'Y') {19 yCount++;20 }21 }22 }2324 // Check conditions25 if (xCount > 0 && xCount == yCount) {26 count++;27 }28 }29 }30 return count;31 }32}
Complexity
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.
Trade-offs
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.
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.
Algorithm
Get the grid dimensions R and C.
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).
Populate the prefix sum arrays by iterating i from 1 to R and j from 1 to C.
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.
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].
Check if prefixX[r+1][c+1] > 0 and prefixX[r+1][c+1] == prefixY[r+1][c+1].
If the conditions are met, increment count.
Return count.
Walkthrough
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.
1class Solution {2 public int numberOfSubmatrices(char[][] grid) {3 int rows = grid.length;4 int cols = grid[0].length;56 int[][] prefixX = new int[rows + 1][cols + 1];7 int[][] prefixY = new int[rows + 1][cols + 1];89 for (int i = 1; i <= rows; i++) {10 for (int j = 1; j <= cols; j++) {11 int isX = (grid[i - 1][j - 1] == 'X') ? 1 : 0;12 int isY = (grid[i - 1][j - 1] == 'Y') ? 1 : 0;1314 prefixX[i][j] = prefixX[i - 1][j] + prefixX[i][j - 1] - prefixX[i - 1][j - 1] + isX;15 prefixY[i][j] = prefixY[i - 1][j] + prefixY[i][j - 1] - prefixY[i - 1][j - 1] + isY;16 }17 }1819 int count = 0;20 for (int r = 1; r <= rows; r++) {21 for (int c = 1; c <= cols; c++) {22 int xCount = prefixX[r][c];23 int yCount = prefixY[r][c];2425 if (xCount > 0 && xCount == yCount) {26 count++;27 }28 }29 }3031 return count;32 }33}
Complexity
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).
Trade-offs
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.
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(RC) to O(C) while maintaining the optimal O(RC) time complexity.
Algorithm
Get grid dimensions R and C.
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.
Initialize count = 0.
Iterate through each row r from 0 to R-1.
For each row, initialize currentX = 0 and currentY = 0. These will act as running prefix sums across columns for the current row.
Iterate through each column c from 0 to C-1.
Update the column-wise prefix sums: colPrefixX[c] and colPrefixY[c] are incremented if grid[r][c] is 'X' or 'Y' respectively.
Update the running prefix sums for the submatrix ending at (r, c): currentX += colPrefixX[c] and currentY += colPrefixY[c].
The variables currentX and currentY now hold the total counts for the submatrix from (0,0) to (r,c).
Check the conditions: if currentX > 0 and currentX == currentY, increment count.
After iterating through all rows and columns, return count.
Walkthrough
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.
1class Solution {2 public int numberOfSubmatrices(char[][] grid) {3 int rows = grid.length;4 int cols = grid[0].length;5 int count = 0;67 // colPrefixX[c] stores the count of 'X' in column c from row 0 to the current row8 int[] colPrefixX = new int[cols];9 int[] colPrefixY = new int[cols];1011 for (int r = 0; r < rows; r++) {12 int currentX = 0; // Running sum of X's for submatrix ending at (r, c)13 int currentY = 0; // Running sum of Y's for submatrix ending at (r, c)14 for (int c = 0; c < cols; c++) {15 // Update column-wise prefix sums for the current row16 if (grid[r][c] == 'X') {17 colPrefixX[c]++;18 } else if (grid[r][c] == 'Y') {19 colPrefixY[c]++;20 }2122 // Update the total counts for the submatrix (0,0) to (r,c)23 currentX += colPrefixX[c];24 currentY += colPrefixY[c];2526 // Check conditions27 if (currentX > 0 && currentX == currentY) {28 count++;29 }30 }31 }32 return count;33 }34}
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.
Trade-offs
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.
Solutions
Solution
1class Solution {2public3 int numberOfSubmatrices(char[][] grid) {4 int m = grid.length, n = grid[0].length;5 int[][][] s = new int[m + 1][n + 1][2];6 int ans = 0;7 for (int i = 1; i <= m; ++i) {8 for (int j = 1; j <= n; ++j) {9 s[i][j][0] = s[i - 1][j][0] + s[i][j - 1][0] - s[i - 1][j - 1][0] +10 (grid[i - 1][j - 1] == 'X' ? 1 : 0);11 s[i][j][1] = s[i - 1][j][1] + s[i][j - 1][1] - s[i - 1][j - 1][1] +12 (grid[i - 1][j - 1] == 'Y' ? 1 : 0);13 if (s[i][j][0] > 0 && s[i][j][0] == s[i][j][1]) {14 ++ans;15 }16 }17 }18 return ans;19 }20}
1class Solution {2public:3 int numberOfSubmatrices(vector<vector<char>> &grid) {4 int m = grid.size(), n = grid[0].size();5 vector<vector<vector<int>>> s(m + 1,6 vector<vector<int>>(n + 1, vector<int>(2)));7 int ans = 0;8 for (int i = 1; i <= m; ++i) {9 for (int j = 1; j <= n; ++j) {10 s[i][j][0] = s[i - 1][j][0] + s[i][j - 1][0] - s[i - 1][j - 1][0] +11 (grid[i - 1][j - 1] == 'X' ? 1 : 0);12 s[i][j][1] = s[i - 1][j][1] + s[i][j - 1][1] - s[i - 1][j - 1][1] +13 (grid[i - 1][j - 1] == 'Y' ? 1 : 0);14 if (s[i][j][0] > 0 && s[i][j][0] == s[i][j][1]) {15 ++ans;16 }17 }18 }19 return ans;20 }21};
1class Solution:2 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
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.
