Equal Row and Column Pairs — Hashing Tuples to Count Grid Symmetries

Problem Statement#

Given an n x n integer matrix grid, return the number of pairs (r, c) such that row r and column c are equal (same values in the same order).

Constraints:

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

Input:  grid = [[3,2,1],[1,7,6],[2,7,7]]
Output: 1

Input:  grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
Output: 3

Why This Problem Matters#

LeetCode 2352 is a textbook hashmap interview question that frequently appears in Google and Amazon onsites. It looks deceptively like a matrix simulation problem, but the optimal solution is pure hashing: convert each row to a tuple, hash it, then walk every column and count how many row tuples it equals.

Why interviewers love this problem: it forces you to recognize that "equal sequences" is the canonical signal to hash an entire sequence as a single key. Candidates who reach for nested loops end up at O(n^3); candidates who reach for a hashmap of tuples land at O(n^2). The gap between the two answers is exactly the gap between a "hire" and a "no-hire" on a hash table FAANG screen.

The pattern generalizes: anywhere you need to count identical sub-arrays, identical paths, or identical rows in a grid, you reach for tuple hashing.

The Core Insight#

Two sequences are equal if and only if they hash to the same key. Python tuples and JavaScript JSON-stringified arrays are both hashable, so we can use them directly as hashmap keys. Count every row in a hashmap, then for each column build the same tuple and look up its count. The total of those lookups is the answer.

Visual Dry Run#

Grid [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]].

Final answer: 3.

Solution (Optimal)#

from collections import Counter
 
class Solution:
    def equalPairs(self, grid: list[list[int]]) -> int:
        n = len(grid)
        row_count = Counter(tuple(row) for row in grid)
        answer = 0
        for c in range(n):
            col_tuple = tuple(grid[r][c] for r in range(n))
            answer += row_count[col_tuple]
        return answer

var equalPairs = function(grid) {
    const n = grid.length;
    const rowCount = new Map();
    for (const row of grid) {
        const key = row.join(',');
        rowCount.set(key, (rowCount.get(key) || 0) + 1);
    }
    let answer = 0;
    for (let c = 0; c < n; c++) {
        const colKey = grid.map(row => row[c]).join(',');
        answer += rowCount.get(colKey) || 0;
    }
    return answer;
};

Time: O(n^2) — building n row tuples and n column tuples each costs O(n). Space: O(n^2) — the hashmap holds up to n distinct row tuples of length n.

Common Mistakes#

• Using lists or arrays as hashmap keys in Python (lists are unhashable). Convert to a tuple.
• Joining columns with no delimiter, which collapses [1,11] and [11,1] into the same key. Always pick a delimiter that cannot appear in the values.
• Iterating over rows and columns naively in O(n^3), comparing every (row, column) pair element by element.
• Forgetting that duplicate rows must be counted with their multiplicity, so a Counter (multi-set) is required, not a Set.
• Off-by-one errors when reading column elements as grid[c][r] instead of grid[r][c].

Interview Tips#

• Verbalize the trade: "I will hash each row as a tuple. That makes lookups O(n) per column, total O(n^2)."
• Mention the alternative O(n^3) brute force first, then justify why hashing is strictly better.
• Highlight that duplicates matter, so use a Counter / Map of frequencies, not a Set.
• Briefly note the JavaScript caveat: arrays are reference-equal, so we serialize them with join.

Follow-up Questions#

• What if entries can be very large strings? Hint: hash by tuple of strings; cost per element grows but algorithm is unchanged.
• What if the grid is rectangular m x n? Hint: rows have length n, columns have length m, so equality only matters when m == n.
• What if you must return the actual (r, c) pairs? Hint: store row indices in a Map<key, list[index]> and pair them with the column index on each match.
• Can you avoid the O(n^2) extra space? Hint: yes if you sort and binary search, but tuple hashing is the standard FAANG answer.
• What if rows are streamed and the matrix doesn't fit in memory? Hint: hash with a rolling polynomial hash and compare hashes lazily.

Key Takeaways#

• LeetCode 2352 is a Google and Amazon favorite that tests tuple-hashing fluency.
• Hash entire sequences when you need to compare equality of ordered collections.
• A Counter of row tuples plus per-column lookup gives O(n^2) time, O(n^2) space.
• Use tuples in Python and join strings in JavaScript to make sequences hashable.
• Counts matter when rows can repeat; reach for a multi-set, not a set.
• The brute-force O(n^3) solution exists but is rarely the expected answer in FAANG interviews.
• This pattern reappears in problems like "find duplicate subtrees" and "group anagrams" — recognize it once and reuse it.