Equal Row and Column Pairs — Medium Problem & Solution

Problem statement

Given an n x n integer matrix grid, return the number of pairs (r, c) such that row r and column c hold the same values in the same order.

Example 1

Input: grid = [[3,2,1],[1,7,6],[2,7,7]]
Output: 1
Explanation: Row 2 is [2,7,7] and column 1 read downwards is [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: Rows 2 and 3 are identical and each matches column 2; row 1 matches column 1.

Example 3

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

Constraints

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

How to solve Equal Row and Column Pairs

Encode each row as one key, tally the keys, then look each column up. Because rows can repeat, the tally — not a set — is what makes the pair count come out right.

Approach

1. Build a map from row-encoding to how many rows produce it.
2. For each column c, read grid[0][c], grid[1][c], … into a sequence and encode it the same way.
3. Add the map's tally for that encoding to the answer.

Why it works

A pair (r, c) qualifies exactly when row r and column c encode identically, so each column contributes one pair for every row sharing its encoding — which is precisely the stored tally.

Complexity

• Time — O(n²)
• Space — O(n²)

Pitfalls

• A set of row encodings loses multiplicity and undercounts whenever two rows are identical.
• Joining values without a separator makes [1,23] and [12,3] collide; join on a delimiter.
• Reading a column left to right instead of top to bottom transposes the comparison.

Reference solution

Python

from typing import List

def equalPairs(grid: List[List[int]]) -> int:
    n = len(grid)
    rows = {}
    for row in grid:
        key = tuple(row)
        rows[key] = rows.get(key, 0) + 1
    total = 0
    for c in range(n):
        key = tuple(grid[r][c] for r in range(n))
        total += rows.get(key, 0)
    return total

JavaScript

var equalPairs = function(grid) {
    var n = grid.length;
    var rows = {};
    for (var r = 0; r < n; r++) {
        var key = grid[r].join(",");
        rows[key] = (rows[key] === undefined ? 0 : rows[key]) + 1;
    }
    var total = 0;
    for (var c = 0; c < n; c++) {
        var col = [];
        for (var i = 0; i < n; i++) col.push(grid[i][c]);
        var ck = col.join(",");
        if (rows[ck] !== undefined) total += rows[ck];
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Count Number of Texts Medium
• Construct String With Repeat Limit Medium
• Minimum Number of Steps to Make Two Strings Anagram II Medium
• Count Vowel Substrings of a String Medium
• Minimum Length of String After Operations Medium
• Sum of Digit Differences of All Pairs Medium