Equal Row and Column Pairs
MedPrompt
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] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly implements the problem statement by iterating through every possible pair of a row and a column and comparing them element by element. It is the most straightforward but least efficient method.
Algorithm
- Initialize a counter
countto 0. - Get the size of the grid,
n. - Iterate through each row
ifrom 0 ton-1. - Inside this loop, iterate through each column
jfrom 0 ton-1. - For the current pair
(row i, column j), check if they are equal by using a third loop. - Iterate
kfrom 0 ton-1. - Compare
grid[i][k](element from rowi) withgrid[k][j](element from columnj). - If at any point
grid[i][k] != grid[k][j], the row and column are not equal. Break the inner loop and move to the next pair. - If the inner comparison loop completes without finding any mismatch, it means the row and column are equal. Increment the
count. - After all pairs have been checked, return
count.
Walkthrough
The brute-force method involves a systematic check of all n*n possible pairs of rows and columns. We use three nested loops. The outer two loops select a row i and a column j. The innermost loop then iterates from k = 0 to n-1 to compare each element of the selected row grid[i][k] with the corresponding element of the selected column grid[k][j]. If all n elements match for a given (i, j) pair, we increment a counter. This process is repeated until all pairs have been checked.
class Solution { public int equalPairs(int[][] grid) { int n = grid.length; int count = 0; for (int i = 0; i < n; i++) { // Iterate through rows for (int j = 0; j < n; j++) { // Iterate through columns boolean isEqual = true; for (int k = 0; k < n; k++) { // Compare elements if (grid[i][k] != grid[k][j]) { isEqual = false; break; } } if (isEqual) { count++; } } } return count; }}Complexity
Time
O(n³). There are three nested loops. The outer two loops iterate through all `n*n` row-column pairs, and the inner loop performs `n` comparisons for each pair.
Space
O(1). The algorithm uses only a constant amount of extra space for loop variables and the counter, regardless of the input grid size.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space, making it very memory-efficient.
Cons
Very inefficient with a cubic time complexity.
Likely to result in a 'Time Limit Exceeded' error on platforms like LeetCode for larger constraints (e.g., n=200).
Solutions
Solution
class Solution {public int equalPairs(int[][] grid) { int n = grid.length; int[][] g = new int[n][n]; for (int j = 0; j < n; ++j) { for (int i = 0; i < n; ++i) { g[i][j] = grid[j][i]; } } int ans = 0; for (var row : grid) { for (var col : g) { int ok = 1; for (int i = 0; i < n; ++i) { if (row[i] != col[i]) { ok = 0; break; } } ans += ok; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.