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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Submatrices With Equal Frequency of X and Y

Difficulty: Medium

Problem 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'.

Key Insights

  • The submatrices must start from the top-left corner (grid[0][0]).
  • We need to maintain a count of 'X' and 'Y' while iterating through possible submatrices.
  • A valid submatrix must have the same number of 'X' and 'Y' characters.
  • We can use a prefix sum approach to efficiently count 'X's and 'Y's in submatrices.

Space and Time Complexity

Time Complexity: O(n^3) - We traverse all possible submatrices, and for each, we need to count 'X's and 'Y's. Space Complexity: O(1) - We use constant space for counters.

Solution

To solve this problem, we can use a prefix sum technique combined with an iterative approach to explore all possible submatrices starting from grid[0][0]. We will maintain counts of 'X' and 'Y' as we expand the boundaries of the submatrices. When both counts are equal and at least one 'X' is present, we increment our result.

  1. Initialize a result counter to zero.
  2. Iterate through all possible bottom-right corners of submatrices starting from (0, 0).
  3. For each corner, maintain counts of 'X' and 'Y' while expanding the submatrix.
  4. Whenever the counts are equal and at least one 'X' is found, increment the result.

Code Solutions

def countSubmatrices(grid):
    m, n = len(grid), len(grid[0])
    result = 0
    
    for r1 in range(m):
        for c1 in range(n):
            x_count = 0
            y_count = 0
            
            for r2 in range(r1, m):
                for c2 in range(c1, n):
                    if grid[r2][c2] == 'X':
                        x_count += 1
                    elif grid[r2][c2] == 'Y':
                        y_count += 1
                    
                    if x_count == y_count and x_count > 0:
                        result += 1
    
    return result
← Back to All Questions