#2352
Equal Row and Column Pairs
Medium HashMap of row signatures
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In an n×n grid, count pairs (row r, column c) where the row and the column contain the same values in the same order.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: count (row, column) pairs with identical values in order.
Why this works: turn each row into a key and count it; then build each column's key and look it up.
Example: [[3,2,1],[1,7,6],[2,7,7]]
column 1 = [2, 7, 7] equals row 2 → 1 pair✦Hints open one at a time
Turn each row into a key (e.g. its values joined into a string).
Count row keys in a map, then build each column's key and look it up.
↗Approach
Store counts of row signatures, then for every column build its signature and add the matching row count.
</>Solution (Java)
import java.util.*;
class Solution {
public int equalPairs(int[][] grid) {
int n = grid.length;
Map<String, Integer> rows = new HashMap<>();
for (int[] row : grid) rows.merge(Arrays.toString(row), 1, Integer::sum);
int pairs = 0;
for (int c = 0; c < n; c++) {
int[] col = new int[n];
for (int r = 0; r < n; r++) col[r] = grid[r][c];
pairs += rows.getOrDefault(Arrays.toString(col), 0);
}
return pairs;
}
}!Common mistake
Using int[] as a map key — arrays use identity, so equal rows don't match. Use Arrays.toString or a List.
Complexity
- Time: O(n²).
- Space: O(n²).
Topic: Hashing
🎬 Episodes 37–39: video coming soon