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.
1#include <stdio.h>
2int countEqualPairs(int n, int grid[n][n]) {
3 int count = 0;
4 for (int i = 0; i < n; i++) {
5 for (int j = 0; j < n; j++) {
6 int match = 1;
7 for (int k = 0; k < n; k++) {
8 if (grid[i][k] != grid[k][j]) {
9 match = 0;
10 break;
11 }
12 }
13 if (match) count++;
14 }
15 }
16 return count;
17}
18
19int main() {
20 int grid[3][3] = {{3, 2, 1}, {1, 7, 6}, {2, 7, 7}};
21 int result = countEqualPairs(3, grid);
22 printf("%d\n", result);
23 return 0;
24}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.
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.
1using System.Collections.Generic;
public class EqualRowColumn {
public static int EqualPairs(int[,] grid) {
int n = grid.GetLength(0);
var rowMap = new Dictionary<string, int>();
for (int i = 0; i < n; i++) {
string row = string.Join(",", Enumerable.Range(0, n).Select(j => grid[i, j]));
if (!rowMap.ContainsKey(row))
rowMap[row] = 0;
rowMap[row]++;
}
int count = 0;
for (int j = 0; j < n; j++) {
string col = string.Join(",", Enumerable.Range(0, n).Select(i => grid[i, j]));
if (rowMap.ContainsKey(col)) {
count += rowMap[col];
}
}
return count;
}
public static void Main() {
int[,] grid = { { 3, 2, 1 }, { 1, 7, 6 }, { 2, 7, 7 } };
Console.WriteLine(EqualPairs(grid));
}
}The C# implementation uses a dictionary to hash and save rows converted to strings, then checks these against columns walked in sequence, totaling equal pairs when matches appear.