Equal Row and Column Pairs

Equal Row and Column Pairs

What is this problem about?

The Equal Row and Column Pairs interview question involves an n x n integer matrix. You need to count the number of pairs (r, c) such that row r and column c are equal. A row and a column are equal if they contain the same elements in the same order. Note that if multiple rows are the same or multiple columns are the same, each combination must be counted.

Why is this asked in interviews?

This is a popular "Medium" problem at companies like Meta and Bloomberg. it tests a candidate's ability to use hash table interview pattern to optimize an O(N^3) brute-force search into O(N^2). It evaluates how you handle multi-dimensional data and whether you can efficiently compare sequences of numbers.

Algorithmic pattern used

The problem is solved using a Frequency Map (Hash Table).

1. Iterate through each row of the matrix.
2. Convert the row into a hashable format (like a string or a tuple) and store its frequency in a Hash Map.
3. Iterate through each column of the matrix.
4. Convert the column into the same hashable format.
5. If the column exists in the Hash Map, add its stored frequency to the total count.

Example explanation

Matrix: [[3, 2, 1] [1, 7, 6] [2, 7, 7]]

1. Rows:
   • [3, 2, 1]: count 1
   • [1, 7, 6]: count 1
   • [2, 7, 7]: count 1
2. Columns:
   • Col 0: [3, 1, 2]. Not in row map.
   • Col 1: [2, 7, 7]. Matches Row 2! Total = 1.
   • Col 2: [1, 6, 7]. Not in row map. Total Pairs: 1.

Common mistakes candidates make

• Brute Force: Using three nested loops (row, col, and element comparison) resulting in O(N^3), which is too slow for large matrices.
• Incorrect Hashing: Using a hash function that doesn't account for the order of elements (e.g., just summing the row).
• Not Counting All Pairs: Only checking if a match exists instead of multiplying frequencies (e.g., if there are 2 identical rows and 3 identical columns that match them, there are 6 pairs total).

Interview preparation tip

In many languages, you can use a Row/Column as a key in a Map directly if you convert it to a tuple. This is much faster than manual string concatenation and avoids potential hashing collisions.