Problem

Given a 0-indexed n x n integer matrix grid, return the number of pairs (ri, cj) such that row ri and column cj are equal.

A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).

Examples

Example 1:

1
2
3
4
5
6

Input:
grid = [[3,2,1],[1,7,6],[2,7,7]]
Output:
 1
Explanation: There is 1 equal row and column pair:
- (Row 2, Column 1): [2,7,7]

Example 2:

1
2
3
4
5
6
7
8

Input:
grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
Output:
 3
Explanation: There are 3 equal row and column pairs:
- (Row 0, Column 0): [3,1,2,2]
- (Row 2, Column 2): [2,4,2,2]
- (Row 3, Column 2): [2,4,2,2]

Constraints:

  • n == grid.length == grid[i].length
  • 1 <= n <= 200
  • 1 <= grid[i][j] <= 105

Solution

Method 1 – Hash Map for Row and Column Serialization

Intuition

The key idea is to serialize each row and column into a tuple or string, so we can easily compare them. By counting the frequency of each row’s serialization, we can efficiently check how many columns match any row by comparing their serialization.

Approach

  1. Serialize each row of grid into a tuple and count its frequency using a hash map.
  2. For each column, serialize it into a tuple and check how many times it appears in the row hash map.
  3. Sum up the counts for all columns to get the total number of equal row and column pairs.

Complexity

  • ⏰ Time complexity: O(n^2), where n is the size of the grid, since we process all rows and columns.
  • 🧺 Space complexity: O(n^2), for storing serialized rows in the hash map.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int equalPairs(int[][] grid) {
        int n = grid.length;
        Map<String, Integer> rowCount = new HashMap<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(grid[i][j]).append(",");
            }
            String key = sb.toString();
            rowCount.put(key, rowCount.getOrDefault(key, 0) + 1);
        }
        int ans = 0;
        for (int j = 0; j < n; j++) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                sb.append(grid[i][j]).append(",");
            }
            String key = sb.toString();
            ans += rowCount.getOrDefault(key, 0);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        int n = grid.size();
        map<vector<int>, int> rowCount;
        for (int i = 0; i < n; ++i) {
            rowCount[grid[i]]++;
        }
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            vector<int> col;
            for (int i = 0; i < n; ++i) {
                col.push_back(grid[i][j]);
            }
            ans += rowCount[col];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def equalPairs(self, grid: list[list[int]]) -> int:
        n = len(grid)
        row_count = {}
        for row in grid:
            key = tuple(row)
            row_count[key] = row_count.get(key, 0) + 1
        ans = 0
        for c in range(n):
            col = tuple(grid[r][c] for r in range(n))
            ans += row_count.get(col, 0)
        return ans