Equal Row and Column Pairs
Problem
Given an n x n integer grid, return the number of pairs (r, c) where the rth row and cth column are identical arrays.
- n == grid.length == grid[i].length
- 1 ≤ n ≤ 200
- 1 ≤ grid[i][j] ≤ 10⁵
Example
grid = [[3,2,1],[1,7,6],[2,7,7]]1The algorithm first counts the frequency of each row represented as a tuple. For example, row 0 is (3,2,1), row 1 is (1,7,6), and row 2 is (2,7,7). Then, for each column, it constructs the column tuple and checks how many times this tuple appears in the row frequency map. For column 0, the tuple is (3,1,2), which does not match any row tuple. For column 1, the tuple is (2,7,7), which matches row 2 once. For column 2, the tuple is (1,6,7), which does not match any row tuple. Summing these matches yields the final count of 1.
Approach
Straightforward Solution
A brute-force approach compares each row with each column directly, resulting in O(n^3) time complexity due to nested loops and element-wise comparisons, which is inefficient for large n.
Core Observation
Two arrays are equal if and only if their elements match exactly in order. Representing rows and columns as tuples allows constant-time equality checks and frequency counting.
Path to Optimal
PreviewThe key insight is to transform each row into a hashable tuple and count their frequencies in a hash map. Then, for each column, convert it into a tuple and query the hash map for how many rows match it…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewBuild a frequency map of all rows as tuples. Then iterate over each column, build its tuple, and sum the counts from the frequency map…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n^2)
Constructing the frequency map requires iterating over all n rows with n elements each (O(n^2)). Similarly, building each column tuple and querying the map takes O(n^2). Hash map lookups are O(1) on average, so total time is O(n^2).
Space
O(n^2)
The frequency map stores up to n unique row tuples, each of length n, resulting in O(n^2) auxiliary space. The column tuples are constructed on the fly and discarded, so they do not add to peak space.
Pattern Spotlight
Hash Maps (Frequency Counting with Tuple Keys)
When needing to compare entire rows or columns for equality efficiently, convert them into immutable tuple keys and use a hash map to count frequencies, enabling O(1) average lookups and reducing nested comparisons.
Solution
| 1 | class Solution: |
| 2 | def equalPairs(self, grid: List[List[int]]) -> int: |
| 3 | n = len(grid) |
| 4 | |
| 5 | row_count = {} |
| 6 | |
| 7 | for row in grid: |
| 8 | key = tuple(row) |
| 9 | row_count[key] = row_count.get(key, 0) + 1 |
| 10 | |
| 11 | count = 0 |
| 12 | |
| 13 | for c in range(n): |
| 14 | column = [] |
| 15 | for r in range(n): |
| 16 | column.append(grid[r][c]) |
| 17 | |
| 18 | column = tuple(column) |
| 19 | count += row_count.get(column, 0) |
| 20 | |
| 21 | return count |
Step-by-Step Solution
Build Frequency Map of Rows as Tuples
| 3 | n = len(grid) |
| 5 | row_count = {} |
| 7 | for row in grid: |
| 8 | key = tuple(row) |
| 9 | row_count[key] = row_count.get(key, 0) + 1 |
Objective
To count how many times each unique row appears by converting rows into immutable tuples and storing their frequencies in a hash map.
Key Insight
Tuples are hashable and can be used as keys in a dictionary, enabling constant-time lookups. By mapping each row to its frequency, the algorithm can quickly determine how many rows match any given column tuple later. This precomputation transforms the problem from repeated comparisons to simple lookups.
Interview Quick-Check
Core Logic
Convert each row to a tuple and increment its count in the hash map to enable O(1) frequency queries.
Common Pitfalls & Bugs
Forgetting to convert rows to tuples before using them as dictionary keys leads to unhashable type errors.
Construct Column Tuples and Accumulate Matching Counts
To iterate over each column, build its tuple representation, and sum the frequencies of matching rows from the precomputed map.
Return the Total Count of Equal Row-Column Pairs
To output the final accumulated count representing the number of equal row-column pairs in the grid.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
count += row_count.get(column, 0)Add the frequency of the column tuple from the row map to the count.
This addition is the critical step that leverages the precomputed row frequencies to count matching pairs in O(1) time per column, reducing the overall complexity from O(n^3) to O(n^2).
key = tuple(row)Convert the current row list into an immutable tuple.
Tuples are hashable and can be used as dictionary keys, enabling efficient frequency counting and lookups.
column = tuple(column)Convert the collected column list into an immutable tuple.
Converting to a tuple enables hash map lookups to quickly find matching rows without element-wise comparison.
Full line-by-line criticality + rationale for all 13 lines available on Pro.
Test Your Understanding
Why is it more efficient to use a hash map of row tuples rather than comparing each row to each column directly?
See the answer with Pro.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Equal Row and Column Pairs from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Equal Row and Column Pairs drill