Problem
Given an n x n integer matrix grid, return the number of pairs(ri, cj) such that the i-th row and j-th column are equal.
A row and column form a pair when they contain the same elements in the same order.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
grid = [[3,2,1],
[1,7,6],
[2,7,7]]Output
1Example 2
Input
grid = [[1,1,1],
[1,1,1],
[1,1,1]]Output
9Solution
This solution uses a HashMap to store the frequency of each row. We convert every row into a string representation and store its occurrence count in the map.We then construct each column and check whether its representation exists in the HashMap. If a column matches a row, we add the frequency of that row to the result. This also handles duplicate rows correctly.
class Solution {
public int equalPairs(int[][] grid) {
int n = grid.length;
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
StringBuilder row = new StringBuilder();
for (int j = 0; j < n; j++) {
row.append(grid[i][j]).append(",");
}
map.put(row.toString(), map.getOrDefault(row.toString(), 0) + 1);
}
int result = 0;
for (int j = 0; j < n; j++) {
StringBuilder column = new StringBuilder();
for (int i = 0; i < n; i++) {
column.append(grid[i][j]).append(",");
}
result += map.getOrDefault(column.toString(), 0);
}
return result;
}
}Complexity
We process every element of the n x n matrix while building the row and column representations, so the time complexity isO(n2).
The HashMap stores up to
n row representations, each containing n elements, so the extra space complexity is O(n2).