LeetCode 2352 - Equal Row and Column Pairs

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Matrix, Simulation

Solution

Problem Understanding

The problem gives us a square matrix grid of size n x n, where every element is an integer. We need to count how many (row, column) pairs are exactly equal.

More specifically, for every row ri and every column cj, we compare the sequence of elements in that row with the sequence of elements in that column. If they contain the same values in the same order, then that pair counts as one valid match.

For example, suppose a row is:

[2, 7, 7]

and a column is also:

[2, 7, 7]

Since every element appears in the same position and order, they are considered equal.

The input is a square matrix:

grid[i] represents the i-th row.
grid[j][i] represents the value at row j and column i.

The output is a single integer, representing the total number of equal row-column pairs.

The constraints are important:

1 <= n <= 200
1 <= grid[i][j] <= 10^5

Since n is at most 200, the matrix contains at most 40,000 cells. This is not extremely large, but comparing every row against every column element by element can still become expensive. A naive solution might work within limits, but we should still look for a cleaner and more efficient approach.

There are also some important observations and edge cases:

Multiple identical rows may exist, and they should each contribute separately to the count.
Multiple identical columns may exist as well.
A matrix of size 1 x 1 is valid, meaning the only row and only column must always match.
The matrix is guaranteed to be square, so we never need to handle rectangular matrices.
Values are always positive integers, so we do not need to consider missing or invalid entries.

A common mistake is forgetting that duplicate rows or duplicate columns contribute multiple times. If a row pattern appears twice and a matching column pattern appears three times, then they contribute 2 × 3 = 6 valid pairs.

Approaches

Brute Force Approach

The most direct solution is to compare every row with every column.

We have n rows and n columns. For each pair (row, column), we compare all n elements one by one.

The process works like this:

Iterate through every row.
Iterate through every column.
Build or simulate the column values.
Compare the row and column element by element.
Increment the answer if they are identical.

This works because the problem definition is straightforward. We simply test every possible pair and count the valid ones.

However, it becomes inefficient because:

There are n² row-column pairs.
Each comparison takes O(n) time.

This results in O(n³) time complexity.

Since n = 200, the worst case is about 8,000,000 operations, which is still manageable, but we can do better conceptually and make the implementation cleaner.

Key Insight for an Optimal Solution

The key observation is that we are repeatedly checking whether a row sequence exists among the columns.

Instead of comparing every row against every column individually, we can treat rows and columns as hashable sequences.

If we convert every row into a tuple and store its frequency in a hash map, then for each column we only need to check whether the same sequence exists among the rows.

For example:

Rows:
[2,4,2,2]
[2,4,2,2]

We can store:

(2,4,2,2) -> 2

Then when we encounter the column:

[2,4,2,2]

we immediately know there are 2 matching rows.

This avoids repeated comparisons and turns sequence matching into efficient hash lookups.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Compare every row with every column element by element
Optimal	O(n²)	O(n²)	Use a hash map to count row patterns and match columns

Algorithm Walkthrough

Optimal Algorithm

Create a hash map to store row frequencies.

We convert every row into a tuple because lists are mutable and cannot be used as dictionary keys in Python. The tuple representation allows us to store row patterns efficiently. 2. Iterate through all rows in the matrix.

For each row, convert it into a tuple and increment its count in the hash map.

For example:

Row map:
(3,1,2,2) -> 1
(1,4,4,5) -> 1
(2,4,2,2) -> 2

Initialize a variable equal_pairs = 0.

This variable will accumulate the total number of matching row-column pairs. 4. Iterate through every column.

To build a column, collect:

grid[0][col]
grid[1][col]
...
grid[n-1][col]

Convert this column into a tuple. 5. Check whether this column tuple exists in the row frequency map.

If it exists, add its frequency to the answer.

This is important because duplicate rows matter.

For example:

Column = (2,4,2,2)
Frequency in rows = 2

We add 2 because both rows form valid pairs. 6. Return the final count.

Why it works

The algorithm works because every row and column is represented by the exact ordered sequence of values. By storing row frequencies in a hash map, we preserve how many times each row pattern appears. Then, for each column, we simply count how many rows share the same sequence.

Since equality is defined as matching elements in the same order, using tuples as keys guarantees exact sequence matching. Every valid row-column pair is counted exactly once.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        n = len(grid)

        # Count occurrences of each row pattern
        row_count = Counter(tuple(row) for row in grid)

        equal_pairs = 0

        # Build each column and check for matching rows
        for col in range(n):
            column = tuple(grid[row][col] for row in range(n))
            equal_pairs += row_count[column]

        return equal_pairs

The implementation begins by creating a frequency map of rows using Counter. Each row is converted into a tuple so it can be used as a dictionary key.

For example:

grid = [
    [2,4,2,2],
    [2,4,2,2]
]

becomes:

{
    (2,4,2,2): 2
}

Next, we iterate through every column index. For each column, we construct a tuple by collecting elements vertically through the matrix.

Instead of comparing against every row manually, we directly look up the column tuple in row_count. If the pattern exists, its frequency is added to the answer.

This makes the implementation concise and efficient while naturally handling duplicate rows.

Go Solution

func equalPairs(grid [][]int) int {
	n := len(grid)

	// Count row frequencies
	rowCount := make(map[string]int)

	for _, row := range grid {
		key := serialize(row)
		rowCount[key]++
	}

	equalPairs := 0

	// Build each column and check matches
	for col := 0; col < n; col++ {
		column := make([]int, n)

		for row := 0; row < n; row++ {
			column[row] = grid[row][col]
		}

		key := serialize(column)
		equalPairs += rowCount[key]
	}

	return equalPairs
}

func serialize(nums []int) string {
	result := ""

	for _, num := range nums {
		result += fmt.Sprintf("%d,", num)
	}

	return result
}

In Go, slices cannot be used as keys in a map because they are not comparable. To solve this, we serialize each row and column into a string representation.

For example:

[2,4,2,2]

becomes:

"2,4,2,2,"

This serialized string acts as the hash key inside the map.

Unlike Python, Go does not have a built-in tuple type or Counter, so we manually maintain a frequency map using map[string]int.

There are no integer overflow concerns here because the maximum number of valid pairs is 200 × 200 = 40,000, which easily fits inside Go's int.

Worked Examples

Example 1

grid = [
    [3,2,1],
    [1,7,6],
    [2,7,7]
]

Step 1: Build row frequency map

Row	Tuple	Count
[3,2,1]	(3,2,1)	1
[1,7,6]	(1,7,6)	1
[2,7,7]	(2,7,7)	1

Resulting map:

{
    (3,2,1): 1,
    (1,7,6): 1,
    (2,7,7): 1
}

Step 2: Check columns

Column Index	Column Values	Match Count	Running Total
0	(3,1,2)	0	0
1	(2,7,7)	1	1
2	(1,6,7)	0	1

Final answer:

Example 2

grid = [
    [3,1,2,2],
    [1,4,4,5],
    [2,4,2,2],
    [2,4,2,2]
]

Step 1: Build row frequency map

Row	Tuple	Count
[3,1,2,2]	(3,1,2,2)	1
[1,4,4,5]	(1,4,4,5)	1
[2,4,2,2]	(2,4,2,2)	2

Step 2: Check columns

Column Index	Column Values	Match Count	Running Total
0	(3,1,2,2)	1	1
1	(1,4,4,4)	0	1
2	(2,4,2,2)	2	3
3	(2,5,2,2)	0	3

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Building row tuples and column tuples each processes `n²` elements
Space	O(n²)	The hash map may store up to `n` row patterns of length `n`

The time complexity is O(n²) because we process every cell in the matrix a constant number of times. Building the row frequency map takes O(n²), and constructing all columns also takes O(n²).

The space complexity is O(n²) because, in the worst case, every row is unique and stored as a tuple of length n.

Test Cases

solution = Solution()

assert solution.equalPairs([[3,2,1],[1,7,6],[2,7,7]]) == 1
# Provided example 1

assert solution.equalPairs([
    [3,1,2,2],
    [1,4,4,5],
    [2,4,2,2],
    [2,4,2,2]
]) == 3
# Provided example 2

assert solution.equalPairs([[1]]) == 1
# Smallest possible matrix

assert solution.equalPairs([
    [1,2],
    [3,4]
]) == 0
# No matching row-column pairs

assert solution.equalPairs([
    [1,2],
    [2,1]
]) == 2
# Every row matches a column

assert solution.equalPairs([
    [1,1],
    [1,1]
]) == 4
# Duplicate rows and columns

assert solution.equalPairs([
    [5,5,5],
    [5,5,5],
    [5,5,5]
]) == 9
# All rows equal all columns

assert solution.equalPairs([
    [1,2,3],
    [1,2,3],
    [3,2,1]
]) == 0
# Duplicate rows but no matching columns

Test Summary

Test	Why
`[[3,2,1],[1,7,6],[2,7,7]]`	Validates example 1
Example 2 matrix	Validates duplicate row counting
`[[1]]`	Smallest boundary case
`[[1,2],[3,4]]`	No matches
`[[1,2],[2,1]]`	Symmetric matrix with full matching
`[[1,1],[1,1]]`	Duplicate rows and columns
All values identical	Maximum duplicate pairing behavior
Duplicate rows but mismatched columns	Prevents false positives

Edge Cases

Single Cell Matrix

A 1 x 1 matrix always has exactly one valid pair because the only row and the only column contain the same single value.

For example:

[[7]]

The implementation handles this naturally. The row tuple (7,) is stored once, and the only column produces the same tuple, resulting in one match.

Duplicate Rows and Columns

This is one of the easiest places to make mistakes. Suppose we have:

[
    [1,1],
    [1,1]
]

There are two identical rows and two identical columns. Every row matches every column:

2 × 2 = 4

A naive implementation that only checks existence instead of frequency could incorrectly return 2. Our implementation correctly stores frequencies in the hash map and adds the total count.

No Matching Pairs

Some matrices contain no equal row-column pairs at all.

For example:

[
    [1,2],
    [3,4]
]

Rows:

(1,2)
(3,4)

Columns:

(1,3)
(2,4)

No sequences match.

The implementation handles this correctly because failed hash lookups simply contribute 0 to the total.

Repeated Values Inside Rows

Rows or columns may contain repeated numbers:

[2,2,2]

A buggy implementation might accidentally compare sets or sorted versions of sequences, which would lose ordering information.

Our approach preserves exact ordering by storing tuples, so:

[1,2,2]

and

[2,1,2]

are treated as different patterns, exactly as required by the problem statement.