Equal row and Column pairs

XXX. Equal Row and Column Pairs

Hash Map

Array Manipulation

Problem Statement:

Given a 2D grid of size n x n, determine how many pairs of rows and columns have the same elements in the same order.

Algorithm:

The algorithm uses a hash map to count occurrences of each row as a string. For each column, the algorithm converts it to a string and checks its count in the hash map. The total count of matches is returned.

1. Create a hash map to keep track of row frequencies by converting each row to a string representation.
2. Iterate through each row in the grid:
• Convert the row to a string using Arrays.toString().
• Store or update the row's frequency in the hash map.
3. Iterate through each column in the grid:
• Extract the column elements into a temporary array.
• Convert the column to a string and check its frequency in the hash map.
• Add the frequency to the total count.
4. Return the total count of matching rows and columns.

Complexity:

Time Complexity: O(n²), where n is the number of rows/columns in the grid. Each row and column is processed once.
Space Complexity: O(n²), for storing rows as strings in the hash map.

Java Implementation:

import java.util.*;

public class Solution {
    public int equalPairs(int[][] grid) {
        int count = 0;
        int n = grid.length;

        // Keep track of the frequency of each row.
        Map rowCounter = new HashMap<>();

        for (int[] row : grid) {
            // Convert the row to a string representation.
            String rowString = Arrays.toString(row);
            // Increment the count for this row in the map.
            rowCounter.put(rowString, 1 + rowCounter.getOrDefault(rowString, 0));
        }

        // Add up the frequency of each column in the map.
        for (int j = 0; j < n; j++) {
            int[] colArray = new int[n];
            // Extract the column as an array.
            for (int i = 0; i < n; ++i)
                colArray[i] = grid[i][j];

            // Convert the column to a string.
            String colString = Arrays.toString(colArray);
            
            // Add the frequency of this column's string representation to the count.
            count += rowCounter.getOrDefault(colString, 0);
        }

        return count;
    }
}