2352. Equal Row and Column Pairs

Medium · solved 2026-10-01 · Open on LeetCode

hash-tablematrixarray

Time O(n²) · Space O(n²)

How to get there

Group by sequence, then multiply

1. Solve it by hand. On LeetCode’s example 2, compare each row with each column, number by number: row 0 equals column 0, and rows 2 and 3 both equal column 2. That is 3 pairs, found by n × n comparisons of n numbers each: O(n³).

2. Ask what a pair really needs. A row and a column pair up exactly when they read the same sequence. So instead of comparing them two at a time, give each sequence a name and compare names. Joining the numbers with a separator, as in "2_4_2_2", gives that name: two sequences are equal exactly when their tokens are, because _ never appears inside a number. A token is a string, so it can be a dict key.

3. Count by token, rows and columns apart. A pair is always one row with one column; two equal rows, or two equal columns, are not a pair. So rows and columns get a dict each: rows[token] says how many rows read it, cols[token] how many columns.

4. Turn the counts into pairs. A token held by a rows and b columns makes a × b pairs, since each of those rows pairs with each of those columns. Every pair has exactly one token, so adding a × b over all tokens counts each pair once. A token missing from either side adds 0.

The reusable recipe: to count matching pairs between two groups, give each item a key, count each group by key, and add the product of the two counts for every key.

Let the variables' meanings write the loop

Variable	Always means
`token`	one row or column, its numbers joined with `_`
`rows`	each token mapped to how many rows read so far have it
`cols`	each token mapped to how many columns read so far have it

Code	What happened	What it restores
`token = "_".join(... self.row(grid, i))`	row `i` is read	its sequence becomes one key
`if token not in rows: rows[token] = 1`, `else: rows[token] += 1`	a row with this token	`rows` counts it, first sighting or repeat
the same lines with `self.col` and `cols`	column `i` is read	`cols` counts it
`sum(rows[token] * cols[token] for token in rows if token in cols)`	both dicts are complete	each token adds its pairs; a token with no column is skipped, a token with no row is never visited

Rows and columns are counted in the same loop because the grid is square: index i reaches row i and column i together.

The method carries over: keep one count per group, so the two numbers a pair needs stay apart until the multiplication.

Alternatives compared

Approach	Time	Space	How it works
Brute force	O(n³)	O(1)	Compare every row with every column, number by number.
Two dicts of tokens (chosen)	O(n²)	O(n²)	Count rows and columns by token, then add `rows × cols` for each token.
One dict, looked up by column	O(n²)	O(n²)	Count the rows only; each column then adds `rows[token]`, the number of rows equal to it.
Tuple keys	O(n²)	O(n²)	`tuple(row)` is hashable, so it can be the key directly, without building a string.

Reading the grid alone takes n² steps, so O(n²) is the best possible. The one-dict version adds the same rows × cols total one column at a time: a token’s rows count gets added once per matching column.

solution.py

class Solution:
    def equalPairs(self, grid: list[list[int]]) -> int:
        n = len(grid) # n x n

        rows, cols = {}, {}

        for i in range(n):
            token = "_".join(str(num) for num in self.row(grid, i))
            if token not in rows:
                rows[token] = 1
            else:
                rows[token] += 1

            token = "_".join(str(num) for num in self.col(grid, i))
            if token not in cols:
                cols[token] = 1
            else:
                cols[token] += 1

        return sum(rows[token] * cols[token] for token in rows if token in cols)

    def row(_, grid: list[list[int]], i: int) -> list[int]:
        return grid[i]

    def col(_, grid: list[list[int]], i: int) -> list[int]:
        return [col[i] for col in grid]

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.