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 at n = 200. That passes here, but the hash-based solution is O(n²), and the gap grows quickly with n.

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


def equalPairs(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 is ~8·10^6 comparisons, which passes. The inner comparison loop is the redundant work that a hash lookup removes; at n = 2000 the count is already 8·10^9.

Approach 2 — Hash the rows

“How many rows equal this column?” is a multiset lookup. Precompute a hash map from row content to its count, and each column resolves in one O(n) hashing step instead of n separate O(n) comparisons. Lists are not hashable, so each row is converted to a tuple. zip applied to the unpacked rows transposes the grid, yielding each column already as a tuple.

from collections import Counter
from typing import List


def equalPairs(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) has count 2 (rows 2 and 3) and column 0 matches row 0, so the lookups sum to 3. The Counter handles duplicate rows without extra code.

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

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) merges rows with common prefixes. Walking a column down the trie either stops at the first mismatch or lands on a node that records how many rows end there. Same asymptotics as hashing, with no dependence on hashing and an early exit on a mismatched prefix.

Inserting the three rows of [[3, 2, 1], [1, 7, 6], [2, 7, 7]] builds this trie (terminal nodes carry count = 1):

flowchart TD
    root((root)) --> a3[3]
    a3 --> a2[2]
    a2 --> a1["1 (count 1)"]
    root --> b1[1]
    b1 --> b7[7]
    b7 --> b6["6 (count 1)"]
    root --> c2[2]
    c2 --> c7[7]
    c7 --> c7b["7 (count 1)"]

from typing import List


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


def equalPairs(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-based double loop when zip(*grid) transposes the grid in one expression and returns each column as a tuple.
• Assuming rows and columns can only match on the diagonal or in symmetric matrices — any (r, c) combination is eligible.

Pattern takeaway

When you would otherwise compare one collection’s items against another’s element by element, convert one side into hashable keys (tuples) and store them in a Counter. Every candidate from the other side then resolves in a single lookup, and duplicate matches are handled by the stored counts. Replacing repeated comparison with one hash build and per-item lookups is the core win of this pattern.