# Equal Row and Column Pairs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/equal-row-and-column-pairs)
Canonical: https://scaleengineer.com/dsa/problems/equal-row-and-column-pairs
**Data structures:** Array, Hash Table, Matrix
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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:**

![](https://assets.glich.co/dsa/equal-row-and-column-pairs/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/equal-row-and-column-pairs/image1.jpg) 

**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].length`
* `1 <= n <= 200`
* `1 <= grid[i][j] <= 105`

# Approaches
## Brute-Force Comparison
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.
**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.
**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).
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Get the size of the grid, `n`.
- Iterate through each row `i` from 0 to `n-1`.
- Inside this loop, iterate through each column `j` from 0 to `n-1`.
- For the current pair `(row i, column j)`, check if they are equal by using a third loop.
- Iterate `k` from 0 to `n-1`.
- Compare `grid[i][k]` (element from row `i`) with `grid[k][j]` (element from column `j`).
- 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`.

## Hashing with a HashMap
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a `HashMap<String, Integer>` to store row frequencies and an integer `count` to 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 `j` from 0 to `n-1`.
- For each column, build its string representation in the same manner as the rows.
- Look up the generated column string in the `rowFrequencies` map.
- If the key exists, add its corresponding value (the frequency) to the total `count`.
- Return the final `count`.

## Optimized Hashing with a Trie
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Define a `TrieNode` class containing a `Map` for children and a `count` field 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 the `count` of the final `TrieNode`.
- Initialize a total `pairCount = 0`.
- **Search Columns:** Iterate through each column index `j` from 0 to `n-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 `count` of the final node to `pairCount`.
- Return `pairCount`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```