666. Equal Row and Column Pairs
You are given an n x n matrix grid of positive integers. Count the pairs (r, c) such that row r read left-to-right is exactly the same sequence as column c read top-to-bottom — same values, same order, same length. Return that count.
Every matching (row index, column index) combination counts: if two identical rows both match two identical columns, that is 4 pairs.
Example 1:
Input: grid = [[2, 7, 9], [9, 4, 4], [5, 1, 4]]
Output: 1
Explanation: Row 1 reads [9, 4, 4] and column 2 (values 9, 4, 4 going down) reads the same, so (r=1, c=2) is a pair. No other row matches any column.
Example 2:
Input: grid = [[2, 2, 5], [2, 2, 5], [5, 5, 9]]
Output: 5
Explanation: Rows 0 and 1 both read [2, 2, 5], and so do columns 0 and 1 — that is 2 × 2 = 4 pairs. Row 2 and column 2 both read [5, 5, 9], adding 1 more.
Constraints:
- n == grid.length == grid[i].length
- 1 ≤ n ≤ 200
- 1 ≤ grid[i][j] ≤ 10⁵
Hints:
The direct check — compare every row against every column element by element — is O(n) work for each of the n² pairs, O(n³) total. Fine at n = 200, but there is a cleaner way.
Two sequences are equal exactly when they have the same fingerprint. Summarize every row as a hashable key (a tuple, or a delimited string) and count how many times each key occurs in a hash map.
Then read each column top-to-bottom, build the same kind of key, and add the map's count for it. Each column pairs with exactly the rows that share its key — multiplicity handled for free.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = [[2, 7, 9], [9, 4, 4], [5, 1, 4]]
Expected output: 1