Equal Row and Column Pairs

Medium
677.

Equal Row and Column Pairs

Equal Row and Column Pairs is a medium coding problem on hash table, matrix and simulation, asked in Amazon, Adobe and Walmart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var equalPairs = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Equal Row and Column Pairs — Solution in Python, Java & C++

Equal Row and Column Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Equal Row and Column Pairs is a medium coding problem on hash table, matrix and simulation, asked in Amazon, Adobe and Walmart interviews.

  • Difficulty: Medium
  • Topics: Hash Table, Matrix, Simulation
  • Asked at: Amazon, Adobe, Walmart
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Equal Row and Column Pairs

  1. Hint 1

    Comparing every row against every column is O(n³) — fine at n = 200, but the hash approach is cleaner.

  2. Hint 2

    Turn each row into a single hashable key and tally the keys.

  3. Hint 3

    Then build each column's key and add its tally to the answer.

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

Java

public static int equalPairs(int[][] grid) {
    int n = grid.length;
    Map<String, Integer> rows = new HashMap<>();
    for (int[] row : grid) {
        StringBuilder sb = new StringBuilder();
        for (int v : row) sb.append(v).append(',');
        String key = sb.toString();
        rows.put(key, rows.getOrDefault(key, 0) + 1);
    }
    int total = 0;
    for (int c = 0; c < n; c++) {
        StringBuilder sb = new StringBuilder();
        for (int r = 0; r < n; r++) sb.append(grid[r][c]).append(',');
        total += rows.getOrDefault(sb.toString(), 0);
    }
    return total;
}

C++

int equalPairs(vector<vector<int>>& grid) {
    int n = (int) grid.size();
    map<vector<int>, int> rows;
    for (auto& row : grid) rows[row]++;
    int total = 0;
    for (int c = 0; c < n; c++) {
        vector<int> col;
        for (int r = 0; r < n; r++) col.push_back(grid[r][c]);
        auto it = rows.find(col);
        if (it != rows.end()) total += it->second;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets · Matrix and Grid Traversal