Equal Row and Column Pairs
Equal Row and Column Pairs is LeetCode 2352 (Medium). Given an n × n grid of integers, count the pairs (r, c) where row r and column c hold the same values in the same order: grid[r][0], grid[r][1], … equals grid[0][c], grid[1][c], ….
- Any row can pair with any column, so
randcneed not be equal. nis at most 200, small enough that even an O(n³) check passes.
- n == grid.length == grid[i].length
- 1 <= n <= 200
- 1 <= grid[i][j] <= 10⁵
Intuition
A row and a column are equal only if they are the same sequence from start to finish. So instead of comparing every row with every column, turn each row into one key: the whole sequence, in order.
- Count the rows: a hash map from each row's key to how many rows have it.
- Look up the columns: build each column's key the same way and add the count stored for it.
A column whose sequence appears in three rows forms three pairs, and three is exactly the count in the map. Building and hashing a key costs O(n), and there are 2n keys, so the work drops from O(n³) to O(n²).
When the question is how many pairs of things are identical, and each thing is a whole sequence, hash the sequence and count. It is the same move as grouping anagrams by a sorted key, or finding duplicate rows in a table.
Approach
Before reading on: in [[3, 1, 2, 2], [1, 4, 4, 5], [2, 4, 2, 2], [2, 4, 2, 2]], find every row that equals some column. How many pairs does column 2 make, and why? Then think of one value that could stand for a whole row so a column can be matched in a single lookup. Aim for O(n²).
Two ways to solve it
Count rows by their sequence, then look up each column.
- Fast: one lookup per column.
- Counts duplicates: identical rows are handled by the stored count.
The answer most interviewers expect.
Check all n² pairs, value by value.
- No extra memory: nothing is stored.
- Early exit: a pair stops at the first mismatch.
The obvious first idea, and fine at n = 200.
The hash map is faster in theory and the usual interview answer, so the steps, code and live demo follow it. The pair-by-pair check is shown after the demo; with n at most 200 it passes too.
Count every row by its sequence
Build Counter(tuple(row) for row in grid). A tuple keeps the values in order and can be used as a dictionary key; a list cannot, because a list could change after it is stored.
Build each column the same way
For column c, collect grid[0][c], grid[1][c], …, grid[n-1][c] into a tuple. It now has the same shape as a row key, so equal sequences give equal keys.
Add the count for each column
Add row_count[column] to the running total, then return the total after the last column. A Counter returns 0 for a key it has never seen, so a column that matches no row adds nothing.
Equal Row and Column Pairs solution in Python | C++ | Java
Compare every row with every column
For every row r and column c, walk k from 0 while grid[r][k] == grid[k][c]. If k reaches n, the whole row matched the whole column and the pair counts. At n = 200 that is at most 8 million comparisons, and most pairs stop after the first value.
Common pitfalls
Reading a row when you meant a column
column = tuple(grid[c][r] for r in range(n))
column = tuple(grid[r][c] for r in range(n))
grid[c][r] with r moving walks along row c, so every "column" is really a row and finds itself in the map. On [[3, 2, 1], [1, 7, 6], [2, 7, 7]] that returns 3, but only row 2 and column 1 match, so the answer is 1.
Gluing values together without a separator
key = "".join(map(str, row))
key = tuple(row) # or ",".join(map(str, row))
Numbers of different lengths run into each other. In [[11, 1], [2, 11]], row 0 becomes "111" and column 1, which is 1, 11, also becomes "111". The code returns 1, but no row equals a column, so the answer is 0.
Keeping a set of rows instead of a count
rows = set(tuple(r) for r in grid) pairs += column in rows
row_count = Counter(tuple(r) for r in grid) pairs += row_count[column]
A set forgets how many rows had each sequence. In [[2, 2], [2, 2]] both rows equal both columns, so there are 4 pairs, but the set holds one key and the code returns 2.
Complexity
Equal Row and Column Pairs FAQ
Why does the C++ code use map instead of unordered_map?
C++ has no built-in hash for vector<int>, so unordered_map<vector<int>, int> does not compile without a custom hasher. map compares vectors instead, which costs O(n log n) per lookup and O(n² log n) in total, fine for n = 200. For a true O(n²), key on a string with a separator between values.