Watch 10 video solutions for Equal Row and Column Pairs, a medium level problem involving Array, Hash Table, Matrix. This walkthrough by Coding Decoded has 8,497 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a 0-indexed n x n integer matrix grid, return the number of pairs (ri, cj) such that row ri and column cj are equal.
A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array).
Example 1:
Input: grid = [[3,2,1],[1,7,6],[2,7,7]] Output: 1 Explanation: There is 1 equal row and column pair: - (Row 2, Column 1): [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: There are 3 equal row and column pairs: - (Row 0, Column 0): [3,1,2,2] - (Row 2, Column 2): [2,4,2,2] - (Row 3, Column 2): [2,4,2,2]
Constraints:
n == grid.length == grid[i].length1 <= n <= 2001 <= grid[i][j] <= 105Problem Overview: You receive an n x n grid. The task is to count how many pairs (ri, cj) exist such that the entire i-th row is identical to the j-th column. Every element must match in order, not just as a set.
Approach 1: Iterative Comparison Approach (O(n^3) time, O(1) space)
The straightforward strategy compares every row with every column. For each row i, iterate through every column j. Then check if grid[i][k] == grid[k][j] for all k from 0 to n-1. If all elements match, increment the count. This works because each row and column can be treated as sequences of length n. The drawback is the nested iteration: n rows × n columns × n element comparisons, giving O(n^3) time. Space stays O(1) since the comparison happens directly on the grid without additional storage. This approach is simple and helps verify correctness before optimizing.
Approach 2: Hashing with Dictionary (O(n^2) time, O(n^2) space)
The key observation: rows and columns are sequences that can be hashed. First, convert every row into a hashable structure such as a tuple and store its frequency in a dictionary. Next, build each column as a tuple and check if it exists in the dictionary. If it does, add the stored frequency to the answer. This works because identical sequences produce identical keys, allowing constant-time lookups. Constructing all rows takes O(n^2), constructing all columns takes another O(n^2), and each lookup is O(1). The result is an overall O(n^2) time complexity with O(n^2) space for storing row signatures. This approach leverages concepts from hash tables and structured traversal of a matrix.
Representing rows and columns as tuples ensures order-sensitive comparison. This matters because [1,2,3] must not match [3,2,1]. Languages without native tuple hashing can serialize rows into strings or arrays before inserting them into the map.
Recommended for interviews: The hashing approach is the expected solution. Interviewers want to see that you recognize repeated sequence comparisons and replace them with hash lookups. Explaining the brute-force comparison first demonstrates understanding of the problem, then transitioning to a dictionary-based optimization shows strong problem-solving skills. The pattern appears often in array and grid problems where rows or columns act as comparable signatures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Comparison | O(n^3) | O(1) | Useful as a baseline solution or when constraints are very small |
| Hashing with Dictionary | O(n^2) | O(n^2) | Best general solution; converts rows and columns to hashable keys for fast lookups |