Equal Row and Column Pairs
Equal Row and Column Pairs: count the pairs (row, column) whose sequences are identical element by element in the same order.
- n == grid.length == grid[i].length
- 1 <= n <= 200
- 1 <= grid[i][j] <= 10⁵
Intuition
Comparing every row against every column is O(n³). Instead, turn each row into a hashable key and count how many rows produce it. Then build each column's key and look it up — the stored count is exactly how many rows match that column, added straight to the answer.
Turning a whole sequence into a hashable key so that equality becomes a lookup is the same canonical-form trick behind Group Anagrams. The tell is 'count pairs that are identical' — whenever equality of composite objects drives the count, hash the object rather than comparing pairwise.
Approach
Before reading on: instead of comparing a row against a column element by element, what single value could represent an entire row so that matching becomes a dictionary lookup? Aim for O(n²).
Why the direct comparison is cubic
There are n rows and n columns, so n² pairs, and verifying one pair means comparing n elements — O(n³) overall. With n up to 200 that is 8 million operations, which happens to pass, but the structure is wasteful: each row is re-read n times. Converting a row to a key once and reusing it removes that repetition and reveals the real shape of the problem.
Rows become keys, columns become lookups
Build a map from row-sequence to occurrence count by walking the rows once. A row must be stored as something hashable — a tuple in Python, a joined string with a separator elsewhere. Then construct each column by reading grid[r][c] for r from 0 to n-1, form the same kind of key, and add whatever count the map holds. Duplicate rows are handled for free: if three rows share a sequence, a matching column contributes 3 to the answer.
Cost
Building the row map is O(n²) — every cell read once — and scanning the columns is another O(n²). Total O(n²) time with O(n²) space for the keys, down from O(n³). The space is the honest cost of hashing whole sequences; if memory were tight you could hash each row to a fixed-size fingerprint instead, at the risk of collisions.
Solution & live demo
Common pitfalls
Using a list as the dictionary key
row_counts[list(row)] += 1
row_counts[tuple(row)] += 1
Lists are mutable and unhashable — Python raises TypeError. A tuple is the immutable equivalent and hashes correctly.
Building the column key with the indices swapped
column = tuple(grid[c][r] for r in range(n))
column = tuple(grid[r][c] for r in range(n))
Column c is formed by fixing the second index and varying the first. Swapping them reads a row again, so the code compares rows with rows and reports the wrong count.
Joining without a separator
key = ''.join(map(str, row))
key = tuple(row) # or '#'.join(map(str, row))
Values run together ambiguously: rows [1,23] and [12,3] both become "123" and are wrongly treated as equal. Use a tuple, or join with a delimiter that cannot appear in the values.
Edge cases
The count map stores multiplicity, so one matching column contributes that many pairs.
Every lookup misses and the answer is 0.
The single row and single column trivially match, giving 1.
Every row equals its corresponding column, so the answer is at least n.
Keys preserve order, so reversed sequences do not match.