Sponsored
Sponsored
The 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.
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.
1public class EqualRowColumn {
2 public static int equalPairs(int[][] grid) {
3 int n = grid.length;
4 int count = 0;
5 for (int i = 0; i < n; i++) {
6 for (int j = 0; j < n; j++) {
7 boolean isEqual = true;
8 for (int k = 0; k < n; k++) {
9 if (grid[i][k] != grid[k][j]) {
10 isEqual = false;
11 break;
12 }
13 }
14 if (isEqual) count++;
15 }
16 }
17 return count;
18 }
19
20 public static void main(String[] args) {
21 int[][] grid = {{3, 2, 1}, {1, 7, 6}, {2, 7, 7}};
22 System.out.println(equalPairs(grid));
23 }
24}The Java code uses a similar logic where nested loops iterate through rows and columns comparing elements. When they match, it increments the count of equal pairs.
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.
Time Complexity: O(n^2) for transposing and additional O(n^3) for comparisons. Space Complexity: O(n^2) for storing the transposed matrix.
1#include <vector>
#include <unordered_map>
using namespace std;
typedef vector<int> vi;
int equalPairs(vector<vi>& grid) {
int n = grid.size();
unordered_map<string, int> rowMap;
for (int i = 0; i < n; ++i) {
string key = "";
for (int j = 0; j < n; ++j) {
key += to_string(grid[i][j]) + ",";
}
rowMap[key]++;
}
int count = 0;
for (int j = 0; j < n; ++j) {
string key = "";
for (int i = 0; i < n; ++i) {
key += to_string(grid[i][j]) + ",";
}
if (rowMap.count(key)) {
count += rowMap[key];
}
}
return count;
}
int main() {
vector<vector<int>> grid = {{3, 2, 1}, {1, 7, 6}, {2, 7, 7}};
cout << equalPairs(grid) << endl;
return 0;
}Using unordered_map for hashing rows, this solution stores rows as hash keys and then checks columns against these keys. Each column conversion matches stored keys to count equal pairs.