Equal Row and Column Pairs — Solution in Python, Java & C++
Equal Row and Column Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Equal Row and Column Pairs is a medium coding problem on hash table, matrix and simulation, asked in Amazon, Adobe and Walmart interviews.
- Difficulty: Medium
- Topics: Hash Table, Matrix, Simulation
- Asked at: Amazon, Adobe, Walmart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an n x n integer matrix grid, return the number of pairs (r, c) such that row r and column c hold the same values in the same order.
Example 1
Input: grid = [[3,2,1],[1,7,6],[2,7,7]]
Output: 1
Explanation: Row 2 is [2,7,7] and column 1 read downwards is [2,7,7].
Example 2
Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
Output: 3
Explanation: Rows 2 and 3 are identical and each matches column 2; row 1 matches column 1.
Example 3
Input: grid = [[1,2],[3,4]]
Output: 0
Constraints
1 <= n <= 200grid.length == grid[i].length == n1 <= grid[i][j] <= 100000
Hints for Equal Row and Column Pairs
Hint 1
Comparing every row against every column is O(n³) — fine at n = 200, but the hash approach is cleaner.
Hint 2
Turn each row into a single hashable key and tally the keys.
Hint 3
Then build each column's key and add its tally to the answer.
How to solve Equal Row and Column Pairs
Encode each row as one key, tally the keys, then look each column up. Because rows can repeat, the tally — not a set — is what makes the pair count come out right.
Approach
- Build a map from row-encoding to how many rows produce it.
- For each column
c, readgrid[0][c], grid[1][c], …into a sequence and encode it the same way. - Add the map's tally for that encoding to the answer.
Why it works
A pair (r, c) qualifies exactly when row r and column c encode identically, so each column contributes one pair for every row sharing its encoding — which is precisely the stored tally.
Complexity
- Time —
O(n²) - Space —
O(n²)
Pitfalls
- A set of row encodings loses multiplicity and undercounts whenever two rows are identical.
- Joining values without a separator makes
[1,23]and[12,3]collide; join on a delimiter. - Reading a column left to right instead of top to bottom transposes the comparison.
Reference solution
Python
from typing import List
def equalPairs(grid: List[List[int]]) -> int:
n = len(grid)
rows = {}
for row in grid:
key = tuple(row)
rows[key] = rows.get(key, 0) + 1
total = 0
for c in range(n):
key = tuple(grid[r][c] for r in range(n))
total += rows.get(key, 0)
return totalJava
public static int equalPairs(int[][] grid) {
int n = grid.length;
Map<String, Integer> rows = new HashMap<>();
for (int[] row : grid) {
StringBuilder sb = new StringBuilder();
for (int v : row) sb.append(v).append(',');
String key = sb.toString();
rows.put(key, rows.getOrDefault(key, 0) + 1);
}
int total = 0;
for (int c = 0; c < n; c++) {
StringBuilder sb = new StringBuilder();
for (int r = 0; r < n; r++) sb.append(grid[r][c]).append(',');
total += rows.getOrDefault(sb.toString(), 0);
}
return total;
}C++
int equalPairs(vector<vector<int>>& grid) {
int n = (int) grid.size();
map<vector<int>, int> rows;
for (auto& row : grid) rows[row]++;
int total = 0;
for (int c = 0; c < n; c++) {
vector<int> col;
for (int r = 0; r < n; r++) col.push_back(grid[r][c]);
auto it = rows.find(col);
if (it != rows.end()) total += it->second;
}
return total;
}JavaScript
var equalPairs = function(grid) {
var n = grid.length;
var rows = {};
for (var r = 0; r < n; r++) {
var key = grid[r].join(",");
rows[key] = (rows[key] === undefined ? 0 : rows[key]) + 1;
}
var total = 0;
for (var c = 0; c < n; c++) {
var col = [];
for (var i = 0; i < n; i++) col.push(grid[i][c]);
var ck = col.join(",");
if (rows[ck] !== undefined) total += rows[ck];
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets · Matrix and Grid Traversal