Description

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).

Example 1:

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

Example 2:

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

Constraints:

  • n == grid.length == grid[i].length
  • 1 <= n <= 200
  • 1 <= grid[i][j] <= 10^5

Solution

In this problem, if we can somehow store combination of numbers in rows in a HashMap, then we can look up those keys when checking columns. The lookup will be constant time. Also, we need HashMap and not HashSet because the same combination of numbers can occur in multiple rows, so we will have to store their frequency too.

Now in order to store a row as a column, we have create them as a string. We can do so using some delimiter between each number.

 1class Solution {
 2    public int equalPairs (int[][] grids) {
 3        int gridsLength = grids.length;
 4        if (grids == null || gridsLength == 0) {
 5            return 0;
 6        }
 7        int count = 0;
 8        Map<String, Integer> map = new HashMap<>();
 9        String currentRow = "";
10        for (int[] grid : grids) {
11            currentRow = String.join(", ", Arrays.stream(grid).mapToObj(String::valueOf).toArray(String[]::new));
12            map.put(currentRow, map.getOrDefault(currentRow, 0) + 1);
13        }
14
15        // Create column as array and check their string representation in map
16        for (int col = 0; col < gridsLength; col++) {
17            int[] columnArray = new int[gridsLength];
18            for (int row = 0; row < gridsLength; row++) {
19                columnArray[row] = grids[row][col];
20            }
21            currentRow = String.join(", ", Arrays.stream(columnArray).mapToObj(String::valueOf).toArray(String[]::new));
22            count += map.getOrDefault(currentRow, 0); // If there are two row, we can have 2 pairs for single matching column
23        }
24        return count;
25    }
26}
  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2) since we are storing in map as key and value pairs