2352. Equal Row and Column Pairs

[songyy5517]

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:

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:

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]

Intuition The problem is to find the number of equal row-column pairs. A simple idea is to store all the columns and their corresponding occurences in a hashmap. Then looping though the matrix by row, for each row, if it exists in the hashmap, then update the number of equal pairs.

[songyy5517]

Approach: HashMap

1. Exception Handling;
2. Loop though the matrix column-wise; For each column, add its elements into a ArrayList, and then put into a HashMap with its occurence;
3. Loop through the matrix row-wise; For each row, add its elements into a ArrayList, then check if it is contained as the key in the HashMap. If so, update the number of equal pairs.
4. Return the number of equal pairs.

Complexity Analysis

• Time complexity: $O(N^2)$ , looping through the whole matrix takses $O(N^2)$ time;
• Space complexity: $O(N^2)$ , additionally define a $O(N^2)$ HashMap to store the elements by column and their occurence.

[songyy5517]

class Solution {
    public int equalPairs(int[][] grid) {
        // Intuition: HashMap.
        // 1. Exception Handling
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;

        // 2. Record all the rows and their occurences.
        HashMap<ArrayList, Integer> cols = new HashMap();
        for (int j = 0; j < grid[0].length; j++){
            ArrayList<Integer> col = new ArrayList();
            for (int i = 0; i < grid.length; i++)
                col.add(grid[i][j]);
            cols.put(col, 1 + cols.getOrDefault(col, 0));
        }

        // 3. Loop through the columns and calculate the number of same pairs
        int res = 0;
        for (int i = 0; i < grid.length; i++){
            ArrayList<Integer> row = new ArrayList();
            for (int j = 0; j < grid[0].length; j++){
                row.add(grid[i][j]);
            }
            if (cols.containsKey(row))
                res += cols.get(row);
        }

        return res;
    }
}   

[songyy5517]

2024/5/17