Equal Row and Column Pairs — Hash Tuple Rows and Columns

Problem 183 · Equal Row and Column Pairs

Difficulty: Medium · Pattern: Hash Tuples

Count pairs (r, c) where row r equals column c in an n×n grid.

Intuition

Hash each row as a tuple, count frequencies. Then for each column (as a tuple), add its row-frequency to the answer.

Solutions

// C++
int equalPairs(vector<vector<int>>& grid) {
    map<vector<int>,int> rowCnt;
    int n = grid.size(), ans = 0;
    for (auto& r : grid) rowCnt[r]++;
    for (int c = 0; c < n; c++) {
        vector<int> col(n);
        for (int r = 0; r < n; r++) col[r] = grid[r][c];
        ans += rowCnt[col];
    }
    return ans;
}

// Java
public int equalPairs(int[][] grid) {
    int n = grid.length, ans = 0;
    Map<String,Integer> rowCnt = new HashMap<>();
    for (int[] row : grid) {
        String key = Arrays.toString(row);
        rowCnt.merge(key, 1, Integer::sum);
    }
    for (int c = 0; c < n; c++) {
        int[] col = new int[n];
        for (int r = 0; r < n; r++) col[r] = grid[r][c];
        ans += rowCnt.getOrDefault(Arrays.toString(col), 0);
    }
    return ans;
}

// JavaScript
var equalPairs = function(grid) {
    const n = grid.length;
    const rowCnt = new Map();
    for (const row of grid) {
        const k = row.join(',');
        rowCnt.set(k, (rowCnt.get(k) || 0) + 1);
    }
    let ans = 0;
    for (let c = 0; c < n; c++) {
        const k = grid.map(r => r[c]).join(',');
        ans += rowCnt.get(k) || 0;
    }
    return ans;
};

# Python
from collections import Counter
def equalPairs(grid):
    n = len(grid)
    rowCnt = Counter(tuple(r) for r in grid)
    return sum(rowCnt[tuple(grid[r][c] for r in range(n))] for c in range(n))

Complexity

Time: O(n²)
Space: O(n²)