Equal Row and Column Pairs
The key idea
A row and a column are equal only if they hold the same numbers in the same order. So treat each row as a fixed sequence (a tuple) and count how many rows look like that. Then read each column top to bottom as its own sequence and ask how many rows already match it. Hashing the whole sequence lets you compare a row and a column in one lookup instead of element by element.
Problem
Given a square integer matrix grid of size n x n, return the number of pairs (row, col) such that row and col are equal. A row and a column are equal if they contain the same elements in the same order, meaning the equal arrays.
Constraints
- n == grid.length == grid[i].length
- 1 <= n <= 200
- 1 <= grid[i][j] <= 10^5
Examples
Input: grid = [[3,2,1],[1,7,6],[2,7,7]]
Output: 1
Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
Output: 3
Complexity
Time: O(n^2) Space: O(n^2)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY
- Majority Element IIMEDIUM