We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Submatrices With Equal Frequency of X and Y

Number: 3492

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

Given a 2D character matrix grid, where each cell is either 'X', 'Y', or '.', count the number of submatrices that:

  • Contain the cell grid[0][0] (i.e. the top‐left cell must be included).
  • Have an equal frequency of 'X' and 'Y'.
  • Contain at least one 'X'.

Since any submatrix that contains grid[0][0] must have its upper‐left corner at (0,0), the problem reduces to counting the number of prefixes (submatrices defined by (0,0) to (i,j)) that meet the other two conditions.

Key Insights

  • Because grid[0][0] must be inside the submatrix, all valid submatrices are prefixes starting at (0,0) and extending to some (i,j).
  • For a prefix submatrix from (0,0) to (i,j), the count of 'X' and 'Y' can be computed incrementally.
  • The conditions translate to:
    • (# of 'X') equals (# of 'Y') in the prefix.
    • (# of 'X') is at least 1 (to ensure that the submatrix contains at least one 'X').
  • A simple two-dimensional iterative approach with cumulative counts is sufficient given the input constraints.

Space and Time Complexity

Time Complexity: O(m * n) where m and n are the number of rows and columns. Space Complexity: O(1) extra space (if we do it in one pass without using extra matrices)

Solution

We use a straightforward approach with two nested loops to examine each prefix submatrix defined by top-left (0,0) and bottom-right (i,j). For each such prefix we keep a running count of the number of 'X' and 'Y'.

  • As we iterate through the grid, update cumulative counts for X and Y.
  • For each cell (i,j), if the cumulative count of 'X' equals that of 'Y' and is non-zero (which ensures at least one 'X' exists), we increment our answer.
  • The algorithm is efficient due to processing each cell exactly once.

Note: Although prefix sum arrays are common for submatrix sum problems, here the submatrix is fixed to start at (0,0) so we can accumulate counts directly in a double loop.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def countSubmatrices(self, grid):
        # Get the dimensions of the grid.
        m = len(grid)
        n = len(grid[0])
        
        # Initialize cumulative counts and result counter.
        x_count = 0
        y_count = 0
        result = 0
        
        # Iterate over each cell treating the submatrix as having top-left (0,0)
        for i in range(m):
            for j in range(n):
                # If current cell contains 'X', increment x_count.
                if grid[i][j] == 'X':
                    x_count += 1
                # If current cell contains 'Y', increment y_count.
                elif grid[i][j] == 'Y':
                    y_count += 1
                # Check the condition: equal number of 'X' and 'Y' and at least one 'X'
                if x_count == y_count and x_count > 0:
                    result += 1
        
        return result

# Example usage:
# grid = ["XY.", "Y.."]
# print(Solution().countSubmatrices(grid))  # Expected output: 3
← Back to All Questions