2352. Equal Row and Column Pairs

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: grid = [[3,2,1],[1,7,6],[2,7,7]] Output: 1

Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]] Output: 3

Solution Approach

Use a hash table to count the frequency of each row, then compare each column with these rows and sum up the counts for matching pairs.

Algorithm

1. Count Row Frequencies: Use a hash table to count the frequency of each row in the matrix.
2. Compare Columns to Rows: For each column, construct an array and compare it with the rows in the hash table.
3. Sum Matching Pairs: Sum the counts of matching row and column pairs to get the final result.

Implement

    class Solution:
        def equalPairs(self, grid: List[List[int]]) -> int:
            res, n = 0, len(grid)
            ct = Counter(tuple(row) for row in grid)
            res = 0
            for j in range(n):
                res += ct[tuple([grid[i][j] for i in range(n)])]
            return res

    //java code
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int equalPairs(int[][] grid) {
        int n = grid.length;
        int result = 0;
        Map<String, Integer> rowCount = new HashMap<>();
        
        // Count row frequencies
        for (int[] row : grid) {
            String rowKey = arrayToString(row);
            rowCount.put(rowKey, rowCount.getOrDefault(rowKey, 0) + 1);
        }
        
        // Compare columns to rows
        for (int j = 0; j < n; j++) {
            int[] colArray = new int[n];
            for (int i = 0; i < n; i++) {
                colArray[i] = grid[i][j];
            }
            String colKey = arrayToString(colArray);
            result += rowCount.getOrDefault(colKey, 0);
        }
        
        return result;
    }

    private String arrayToString(int[] array) {
        StringBuilder sb = new StringBuilder();
        for (int num : array) {
            sb.append(num).append(",");
        }
        return sb.toString();
    }
}

    

Twitter  facebook  Email