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] <= 105The straightforward way to solve the problem is by iteratively comparing each row with every column to determine if they are equal. This approach requires looping through each pair of row and column and verifying the elements one by one.
This C code iterates over each row and column pair and compares their elements. If a pair matches, it increments the count. The algorithm first checks each row against every column using two nested loops and a third loop for element-wise comparison.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3), as it involves comparing elements for each pair. Space Complexity: O(1), since no extra data structures are used except for counters.
By converting rows and columns into hashable objects (such as tuples in Python or strings in other languages), we can store their occurrences in a dictionary or a hash map. This facilitates a more efficient comparison by checking the presence of corresponding row and column hashes in the stored data structure.
By transposing the matrix first, each row in the original matrix can be compared directly with the columns of the transposed matrix. A helper function is used to compare arrays element by element.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) for transposing and additional O(n^3) for comparisons. Space Complexity: O(n^2) for storing the transposed matrix.
| Approach | Complexity |
|---|---|
| Iterative Comparison Approach | Time Complexity: O(n^3), as it involves comparing elements for each pair. Space Complexity: O(1), since no extra data structures are used except for counters. |
| Hashing with Dictionary | Time Complexity: O(n^2) for transposing and additional O(n^3) for comparisons. Space Complexity: O(n^2) for storing the transposed matrix. |
Leetcode 2352 Equal Row and Column Pairs | Easy Peasy Maps • Coding Decoded • 7,467 views views
Watch 9 more video solutions →Practice Equal Row and Column Pairs with our built-in code editor and test cases.
Practice on FleetCode