Equal Row and Column Pairs
Medium · Matrix · Array · Hash Table · Matrix · Simulation
Problem
You are given an n × n integer matrix grid. Count the pairs (r, c) for which row r and column c are equal: they hold the same values in the same order, grid[r][k] == grid[k][c] for every k.
Every row is compared with every column, so equal rows (or equal columns) each form their own pairs.
Examples
Input: grid = [[3, 2, 1], [1, 7, 6], [2, 7, 7]] Output: 1
Row 2 [2, 7, 7] equals column 1 [2, 7, 7].
Input: grid = [[3, 1, 2, 2], [1, 4, 4, 5], [2, 4, 2, 2], [2, 4, 2, 2]] Output: 3
Row 0 equals column 0, and rows 2 and 3 (both [2, 4, 2, 2]) each equal column 2.
Input: grid = [[1, 2], [3, 4]] Output: 0
The columns are [1, 3] and [2, 4]; neither row matches.
Constraints
- n == grid.length == grid[i].length
- 1 <= n <= 200
- 1 <= grid[i][j] <= 10^5
Approaches
- Transpose and compare every pair — time O(n³), space O(n²)
Follow-up
What if columns are read from the bottom up? And in a matrix that need not be square, how many pairs of rows are identical?
Related problems
Start free on Cariara · Coding problems · System design studio
