Rows That Match a Column

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 row_col_matches(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 rowColMatches(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 rowColMatches(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 rowColMatches(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;
}

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