Equal Row and Column Pairs

Problem

You’re given an n x n integer matrix grid. Count the pairs (r, c) such that row r, read left to right, is element-for-element identical to column c, read top to bottom. Every matching (row index, column index) combination counts, including repeats when duplicate rows or columns match.

Examples

• grid = [[3, 2, 1], [1, 7, 6], [2, 7, 7]] → 1 — row 2 is [2, 7, 7] and column 1 is [2, 7, 7]; no other pair matches.
• grid = [[3, 1, 2, 2], [1, 4, 4, 5], [2, 4, 2, 2], [2, 4, 2, 2]] → 3 — row 0 matches column 0, and rows 2 and 3 (both [2, 4, 2, 2]) each match column 2.
• grid = [[5]] → 1 — the single row equals the single column.

Constraints

• 1 <= n <= 200
• 1 <= grid[i][j] <= 10^5

Comparing every row against every column element-by-element is O(n³) ≈ 8·10^6 operations — passable here, but the intended hash-based solution is O(n²), and the gap widens fast as n grows.

Think about it first

TL;DR

Count row tuples in a hash map, then look each column up — O(n²) time, O(n²) space.

Approach 1 — Brute force

For every (row, column) pair, compare the n elements directly.

from typing import List


class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        n = len(grid)
        total = 0
        for r in range(n):
            for c in range(n):
                if all(grid[r][k] == grid[k][c] for k in range(n)):
                    total += 1
        return total

Complexity: O(n³) time, O(1) space.

At n = 200 that’s ~8·10^6 comparisons — it squeaks by here, but the whole comparison loop is redundant work that a hash lookup replaces, and n = 2000 would already be 8·10^9.

Approach 2 — Hash the rows

The insight: “does this column equal some row, and how many?” is a multiset membership question — precompute a hash map from row content to multiplicity, and each column resolves in one O(n) hashing step instead of n separate O(n) comparisons. Lists aren’t hashable, so each row must be frozen into a tuple; zip applied to the unpacked rows yields the columns (transposition), already as tuples.

from collections import Counter
from typing import List


class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        row_counts = Counter(tuple(row) for row in grid)
        return sum(row_counts[col] for col in zip(*grid))

Walkthrough on grid = [[3, 2, 1], [1, 7, 6], [2, 7, 7]]:

1. row_counts = {(3, 2, 1): 1, (1, 7, 6): 1, (2, 7, 7): 1}.
2. Columns via zip: (3, 1, 2), (2, 7, 7), (1, 6, 7).
3. Lookups: (3, 1, 2) → 0, (2, 7, 7) → 1, (1, 6, 7) → 0. Total 1.

On the question’s second example, column 2 = (2, 4, 2, 2) finds multiplicity 2 (rows 2 and 3), and column 0 finds row 0, so the counts naturally sum to 3 — duplicates are free with a Counter.

Complexity: O(n²) time (every cell is hashed a constant number of times), O(n²) space for the tuples and map.

Approach 3 — Trie of rows

The insight: rows that share a prefix can share storage and comparison work. A trie (prefix tree — a tree whose root-to-node paths spell out sequence prefixes) stores all rows with shared prefixes merged; walking a column down the trie either dies at the first mismatch or lands on a node that knows how many rows end there. Same asymptotics as hashing, but no reliance on hashing at all and early exit on mismatched prefixes.

from typing import List


class TrieNode:
    def __init__(self) -> None:
        self.children: dict[int, "TrieNode"] = {}
        self.count = 0


class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        n = len(grid)
        root = TrieNode()
        for row in grid:
            node = root
            for v in row:
                if v not in node.children:
                    node.children[v] = TrieNode()
                node = node.children[v]
            node.count += 1

        total = 0
        for c in range(n):
            node = root
            for r in range(n):
                nxt = node.children.get(grid[r][c])
                if nxt is None:
                    break
                node = nxt
            else:
                total += node.count
        return total

Walkthrough on grid = [[3, 2, 1], [1, 7, 6], [2, 7, 7]]:

1. Insert rows: paths 3→2→1, 1→7→6, 2→7→7, each terminal node with count = 1.
2. Column 0 = 3, 1, 2: from the root take 3, then look for 1 — the node after 3 only has child 2 → dead end, contributes 0.
3. Column 1 = 2, 7, 7: path 2→7→7 exists and ends with count = 1 → total 1.
4. Column 2 = 1, 6, 7: after 1 there is only child 7 → dead end. Answer 1.

Complexity: O(n²) time, O(n²) space in the worst case (no shared prefixes).

Common pitfalls

• Comparing a row list to a zip column tuple with == — [2, 7, 7] != (2, 7, 7) in Python, a silent always-false bug; freeze both sides to tuples.
• Counting each matching content once instead of each (row, column) pair — duplicate rows matching one column must count multiple times, which is why the map stores multiplicities, not a set.
• Building columns with an index-juggling double loop when zip(*grid) does the transpose in one expression (and gets the tuples for free).
• Assuming rows and columns can only match on the diagonal or in symmetric matrices — any (r, c) combination is eligible.

Pattern takeaway

When you’d otherwise compare one collection’s items against another’s element-by-element, freeze one side into hashable keys (tuples) and put it in a Counter — every candidate from the other side then resolves in a single lookup, and duplicate matches are handled by storing multiplicities. Turning “compare against everything” into “hash once, look up once” is the signature O(n·m) → O(n + m)-style win of this pattern.