Abstract / Summary

Count all submatrices where the number of x equals the number of y.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 53% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Matrix
• Prefix Sum

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation computes how many sub-matrices of a rectangular character grid contain an equal number of the letters X and Y, with the additional requirement that each counted sub-matrix must end at the current row and column. The algorithm walks the grid once, maintaining cumulative counts per column and updating the answer on the fly. By aggregating information column-wise, the solution avoids enumerating every possible sub-matrix explicitly.

Core Logic

Initialization

result = 0
height = len(grid)
width  = len(grid[0])
x = [0] * width
y = [0] * width

Two one-dimensional arrays, x and y, store the running totals of X and Y occurrences for each column up to the current row. The result accumulator holds the final count.

Row-wise processing

for row in grid:
    newX = 0
    newY = 0
    for i, cell in enumerate(row):
        c = ord(cell)
        if   c == 88:          # "X"
            newX += 1
        elif c == 89:          # "Y"
            newY += 1
        x[i] += newX
        y[i] += newY
        result += x[i] and (x[i] == y[i])

The outer loop iterates over each row. Inside, newX and newY accumulate the number of X and Y characters encountered so far in the current row. For each cell, the character code is compared against the ASCII values of X (88) and Y (89), which is faster than string comparison.

The cumulative column totals are updated by adding the row-wise counters newX and newY to x[i] and y[i]. The expression x[i] and (x[i] == y[i]) contributes 1 to result precisely when the column’s cumulative X count is non-zero and matches the cumulative Y count, indicating a balanced sub-matrix ending at this cell.

Final return

return result

After all rows have been processed, result contains the total number of qualifying sub-matrices.

Edge Cases Handled

The algorithm naturally accommodates rows that contain only X, only Y, or a mixture of both, because the per-column counters are updated incrementally regardless of the distribution. When a row contains no X or Y, the inner counters newX and newY remain zero, leaving the column totals unchanged and ensuring that no false positives are added to result.

If a column never sees an X, the condition x[i] and (x[i] == y[i]) prevents counting sub-matrices that would otherwise have a zero X count but a matching zero Y count, thereby respecting the requirement that both letters must be present.

The code also works correctly when the grid consists of a single row or a single column, because the cumulative logic collapses to a simple linear scan in those dimensions.

Performance Optimizations

The solution achieves high efficiency by:

• Maintaining only two integer arrays of length equal to the grid width, eliminating the need for a full two-dimensional prefix-sum matrix.
• Updating column totals in place, which reduces memory traffic and keeps the cache footprint small.
• Using ord(cell) and direct integer comparison against ASCII codes instead of string equality checks, which cuts down on interpreter overhead.
• Combining the balance check and result increment into a single expression, avoiding extra branching.

Because each cell is visited exactly once and all operations inside the loops are constant-time arithmetic, the implementation runs in linear time relative to the number of cells, with a modest and predictable memory usage proportional to the grid width.

Imagine you are looking at a big grid full of little blocks, almost like a colorful game board. Some of these blocks have an X on them and others have a Y on them. The computer wants to find all the special rectangles hiding inside this grid where the number of X blocks is exactly the same as the number of Y blocks.

To solve this, the computer starts at the very top left corner and walks through the grid one row at a time. It keeps two little notebooks to remember what it has seen so far. One notebook counts how many X blocks it has passed as it moves across and down, and the other notebook does the same for the Y blocks.

As the computer moves to each spot in the grid, it adds up the X marks and the Y marks it has collected. It checks if it has found any X blocks yet and if the total number of X blocks is the same as the total number of Y blocks. Every time the computer sees those two numbers match, it puts a point in a big jar to keep track of a successful rectangle. It continues this process until it has looked at every single spot in the garden of blocks, finishing with a total count of all those equal pairings found along the way.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python		Java	C++			TS
	WalkCCC	Python		Java	C++
	leetcode.ca	Python		Java	C++	Go	Rust	TS
	Progiez	Python		Java	C++
github	charles-wangkai			Java
	everthis		JS
	fsq	Python
	withaarzoo				C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	Python
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality