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).
This approach optimizes the comparison by pre-processing the rows. We convert each row into a canonical representation (like a string) and store its frequency in a HashMap. Then, for each column, we generate its string representation and look up how many rows match it, avoiding the O(n) comparison for each pair.
Algorithm
- Initialize a
HashMap<String, Integer>to store row frequencies and an integercountto 0. - Iterate through each row of the
grid. - For each row, convert it into a unique string representation (e.g., by joining elements with a comma) and store it in the HashMap, incrementing its frequency count.
- After processing all rows, iterate through each column index
jfrom 0 ton-1. - For each column, build its string representation in the same manner as the rows.
- Look up the generated column string in the
rowFrequenciesmap. - If the key exists, add its corresponding value (the frequency) to the total
count. - Return the final
count.
Walkthrough
Instead of repeatedly comparing rows and columns, we can do it in two passes. In the first pass, we iterate through each row, create a unique string key for it (e.g., "3,2,1,"), and store how many times this exact row appears in a HashMap.
In the second pass, we iterate through each column. For each column, we construct its string key in the same way. We then check our HashMap for this key. If the key exists, it means the current column is identical to one or more rows. The value associated with the key tells us exactly how many rows it matches, so we add this value to our total count. This reduces the overall time complexity from cubic to quadratic.
import java.util.HashMap;import java.util.Map; class Solution { public int equalPairs(int[][] grid) { int n = grid.length; int count = 0; Map<String, Integer> rowFrequencies = new HashMap<>(); // Step 1: Process all rows and store their frequencies for (int[] row : grid) { StringBuilder sb = new StringBuilder(); for (int val : row) { sb.append(val).append(","); } String rowString = sb.toString(); rowFrequencies.put(rowString, rowFrequencies.getOrDefault(rowString, 0) + 1); } // Step 2: Process all columns and count matches for (int j = 0; j < n; j++) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { sb.append(grid[i][j]).append(","); } String colString = sb.toString(); count += rowFrequencies.getOrDefault(colString, 0); } return count; }}Complexity
Time
O(n²). The first pass to populate the map involves iterating through `n` rows and building a string of length O(n) for each, taking O(n²) time. The second pass does the same for `n` columns, also taking O(n²) time.
Space
O(n²). In the worst case, all `n` rows are unique. Each row's string representation has a length proportional to `n` (considering the digits of the numbers). The HashMap would store `n` keys, each of average length O(n), leading to O(n²) space.
Trade-offs
Pros
Significantly more efficient than the brute-force approach, with a quadratic time complexity.
Relatively easy to implement using standard library data structures.
Cons
Requires extra space to store the HashMap, which can be up to O(n²) in the worst case.
String creation and hashing can add some overhead.
This is a highly optimized approach that uses a Trie (Prefix Tree) data structure. Instead of converting rows and columns to strings, we insert the integer sequences of rows directly into the Trie. Then, we can efficiently search for each column sequence in the Trie to find the number of matching rows.
Algorithm
- Define a
TrieNodeclass containing aMapfor children and acountfield to mark the end of a sequence. - Initialize a
TrieNode root. - Insert Rows: Iterate through each row in the
grid. For each row, traverse the Trie from the root, inserting the sequence of integers. At the end of each row's path, increment thecountof the finalTrieNode. - Initialize a total
pairCount = 0. - Search Columns: Iterate through each column index
jfrom 0 ton-1. For each column, traverse the Trie from the root following the sequence of integers in that column (grid[0][j], grid[1][j], ...). - If the path for a column is completely found in the Trie, add the
countof the final node topairCount. - Return
pairCount.
Walkthrough
A Trie is a natural fit for matching sequences. We can build a Trie where each path from the root represents a sequence of integers. First, we populate the Trie with all the rows from the grid. We iterate through each row and insert its integer sequence into the Trie. A special counter at each node that marks the end of a row is incremented. This counter will store the frequency of that specific row. Next, we iterate through each column of the grid. For each column, we treat it as a sequence of integers and search for it in the Trie. If we find a complete path in the Trie corresponding to the column sequence, the counter at the final node tells us exactly how many rows are identical to this column. We add this count to our total result. This method avoids the overhead of string manipulation and can be more performant in practice.
import java.util.HashMap;import java.util.Map; class TrieNode { Map<Integer, TrieNode> children = new HashMap<>(); int count = 0;} class Solution { public int equalPairs(int[][] grid) { int n = grid.length; TrieNode root = new TrieNode(); // Step 1: Insert all rows into the Trie for (int[] row : grid) { TrieNode current = root; for (int val : row) { current.children.putIfAbsent(val, new TrieNode()); current = current.children.get(val); } current.count++; } int pairCount = 0; // Step 2: Search for each column in the Trie for (int j = 0; j < n; j++) { TrieNode current = root; for (int i = 0; i < n; i++) { int val = grid[i][j]; if (!current.children.containsKey(val)) { current = null; // Path does not exist break; } current = current.children.get(val); } if (current != null) { pairCount += current.count; } } return pairCount; }}Complexity
Time
O(n²). Inserting `n` rows of length `n` into the Trie takes O(n*n). Searching for `n` columns of length `n` also takes O(n*n).
Space
O(n²). In the worst case, where all prefixes of all rows are unique (e.g., a grid of all unique numbers), the number of nodes in the Trie can be up to the total number of elements, which is n*n.
Trade-offs
Pros
Very efficient O(n²) time complexity.
Avoids the overhead of string creation, concatenation, and hashing, which can be faster in practice than the HashMap approach.
Elegant solution for sequence matching problems.
Cons
More complex to implement than the HashMap approach.
Space complexity is still O(n²) in the worst case, similar to the HashMap approach.
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; }}class Solution {public: int equalPairs(vector<vector<int>> &grid) { int n = grid.size(); vector<vector<int>> g(n, vector<int>(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 (auto &row : grid) { for (auto &col : g) { ans += row == col; } } return ans; }};class Solution: def equalPairs(self, grid: List[List[int]]) -> int: g = [list(col) for col in zip(* grid)] return sum(row == col for row in grid for col in g)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.