Equal Row and Column Pairs

medium matrix hash map

Problem

Given an n × n grid, count pairs (r, c) such that row r read left-to-right equals column c read top-to-bottom. Hash each row vector to its frequency, then walk the columns and look each up.

Inputgrid = [[3,2,1],[1,7,6],[2,7,7]]

Output1

Row 2 = [2,7,7] equals column 2 read top-to-bottom = [1,6,7]? No — try the visualization for the actual count.

grid (rows by ';', cells by ',')

from collections import Counter
def equal_pairs(grid):
    n = len(grid)
    freq = Counter(tuple(r) for r in grid)
    count = 0
    for c in range(n):
        col = tuple(grid[r][c] for r in range(n))
        count += freq[col]
    return count

function equalPairs(grid) {
  const n = grid.length;
  const freq = new Map();
  for (const row of grid) {
    const key = row.join(",");
    freq.set(key, (freq.get(key) || 0) + 1);
  }
  let count = 0;
  for (let c = 0; c < n; c++) {
    const col = grid.map(r => r[c]).join(",");
    count += freq.get(col) || 0;
  }
  return count;
}

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

int equalPairs(vector<vector<int>>& grid) {
    int n = grid.size();
    map<vector<int>, int> freq;
    for (auto& row : grid) freq[row]++;
    int count = 0;
    for (int c = 0; c < n; c++) {
        vector<int> col(n);
        for (int r = 0; r < n; r++) col[r] = grid[r][c];
        count += freq.count(col) ? freq[col] : 0;
    }
    return count;
}

Explanation

We want to count (row, column) pairs where the row, read left to right, looks identical to the column, read top to bottom. The smart move is to remember every row in a lookup table, then ask each column "does a matching row exist?"

First we turn each row into a hashable key (a tuple, or a comma-joined string) and store how many times that exact sequence appears in a frequency map. Two rows can be identical, so we keep counts rather than a plain set.

Then we walk every column, build the same kind of key from its top-to-bottom values, and look it up in the row map. The stored count is exactly how many rows match this column, so we add that count to the answer.

Example: with the active input grid = [[3,1,2],[1,7,7],[2,6,7]], column 0 reads [3,1,2] which matches row 0, contributing 1 to the count. Each column lookup adds the number of equal rows it finds.

Because every lookup is instant, we avoid comparing every row against every column cell by cell, doing the work in roughly grid-size time.

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