What pattern does Equal Row and Column Pairs use?

The Pattern: Hash Maps (Frequency Counting with Tuple Keys) The Heuristic: When needing to compare entire rows or columns for equality efficiently, convert them into immutable tuple keys and use a hash map to count frequencies, enabling O(1) average lookups and reducing nested comparisons.

Equal Row and Column Pairs - LeetCode Solution

Q: What is the time complexity of Equal Row and Column Pairs?

O(n^2). Constructing the frequency map requires iterating over all n rows with n elements each (O(n^2)). Similarly, building each column tuple and querying the map takes O(n^2). Hash map lookups are O(1) on average, so total time is O(n^2).

Problem

Given an n x n integer grid, return the number of pairs (r, c) where the rth row and cth column are identical arrays.

n == grid.length == grid[i].length
1 ≤ n ≤ 200
1 ≤ grid[i][j] ≤ 10⁵

Example

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

Output: 1

The algorithm first counts the frequency of each row represented as a tuple. For example, row 0 is (3,2,1), row 1 is (1,7,6), and row 2 is (2,7,7). Then, for each column, it constructs the column tuple and checks how many times this tuple appears in the row frequency map. For column 0, the tuple is (3,1,2), which does not match any row tuple. For column 1, the tuple is (2,7,7), which matches row 2 once. For column 2, the tuple is (1,6,7), which does not match any row tuple. Summing these matches yields the final count of 1.

Approach

Straightforward Solution

A brute-force approach compares each row with each column directly, resulting in O(n^3) time complexity due to nested loops and element-wise comparisons, which is inefficient for large n.

Core Observation

Two arrays are equal if and only if their elements match exactly in order. Representing rows and columns as tuples allows constant-time equality checks and frequency counting.

Path to Optimal

The key insight is to transform each row into a hashable tuple and count their frequencies in a hash map. Then, for each column, convert it into a tuple and query the hash map for how many rows match it. This reduces the problem to O(n^2) time, as each row and column is processed once, and lookups are O(1) on average.

Optimal Approach

Build a frequency map of all rows as tuples. Then iterate over each column, build its tuple, and sum the counts from the frequency map. Return the total sum as the number of equal row-column pairs.

Time

O(n^2)

Constructing the frequency map requires iterating over all n rows with n elements each (O(n^2)). Similarly, building each column tuple and querying the map takes O(n^2). Hash map lookups are O(1) on average, so total time is O(n^2).

Space

O(n^2)

The frequency map stores up to n unique row tuples, each of length n, resulting in O(n^2) auxiliary space. The column tuples are constructed on the fly and discarded, so they do not add to peak space.

Solution

1class Solution:
2    def equalPairs(self, grid: List[List[int]]) -> int:
3        n = len(grid)
4
5        row_count = {}
6
7        for row in grid:
8            key = tuple(row)
9            row_count[key] = row_count.get(key, 0) + 1
10
11        count = 0
12
13        for c in range(n):
14            column = []
15            for r in range(n):
16                column.append(grid[r][c])
17
18            column = tuple(column)
19            count += row_count.get(column, 0)
20
21        return count

Step-by-Step Solution

1

Build Frequency Map of Rows as Tuples

3n = len(grid)
5row_count = {}
7for row in grid:
8    key = tuple(row)
9    row_count[key] = row_count.get(key, 0) + 1

Objective

To count how many times each unique row appears by converting rows into immutable tuples and storing their frequencies in a hash map.

Key Insight

Tuples are hashable and can be used as keys in a dictionary, enabling constant-time lookups. By mapping each row to its frequency, the algorithm can quickly determine how many rows match any given column tuple later. This precomputation transforms the problem from repeated comparisons to simple lookups.

Interview Quick-Check

Core Logic

Convert each row to a tuple and increment its count in the hash map to enable O(1) frequency queries.

Common Pitfalls & Bugs

Forgetting to convert rows to tuples before using them as dictionary keys leads to unhashable type errors.

2

Construct Column Tuples and Accumulate Matching Counts

11count = 0
13for c in range(n):
  column = []
  for r in range(n):
      column.append(grid[r][c])
  column = tuple(column)
  count += row_count.get(column, 0)

Objective

To iterate over each column, build its tuple representation, and sum the frequencies of matching rows from the precomputed map.

Key Insight

By constructing each column as a tuple, the algorithm leverages the precomputed row frequency map to count matches in O(1) average time per column. This avoids costly element-wise comparisons for every row-column pair and efficiently accumulates the total count of equal pairs.

Interview Quick-Check

Core Logic

For each column, build a tuple of its elements and add the frequency of matching rows from the hash map to the total count.

State & Boundaries

Iterate columns from 0 to n-1 and rows from 0 to n-1 to correctly build column tuples.

Common Pitfalls & Bugs

Not converting the column list to a tuple before lookup causes key errors or misses matches.

3

Return the Total Count of Equal Row-Column Pairs

21	`return count`

Objective

To output the final accumulated count representing the number of equal row-column pairs in the grid.

Key Insight

After summing frequencies for all columns, the count accurately reflects all pairs where the row and column arrays are identical. Returning this value completes the solution.

Interview Quick-Check

Core Logic

Return the accumulated count after processing all columns to provide the final answer.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 19 Critical

count += row_count.get(column, 0)

Add the frequency of the column tuple from the row map to the count.

This addition is the critical step that leverages the precomputed row frequencies to count matching pairs in O(1) time per column, reducing the overall complexity from O(n^3) to O(n^2).

Line 8 Critical

key = tuple(row)

Convert the current row list into an immutable tuple.

Tuples are hashable and can be used as dictionary keys, enabling efficient frequency counting and lookups.

Line 18 Critical

column = tuple(column)

Convert the collected column list into an immutable tuple.

Converting to a tuple enables hash map lookups to quickly find matching rows without element-wise comparison.

Line 5 Core

row_count = {}

Initialize a dictionary to count frequencies of row tuples.

This dictionary is the core data structure enabling O(1) average lookups of how many rows match a given tuple, transforming the problem into a frequency counting task.

Line 9 Core

row_count[key] = row_count.get(key, 0) + 1

Increment the frequency count for the current row tuple.

Updating the count ensures that duplicate rows are accounted for, allowing the algorithm to handle multiple identical rows correctly.

Line 16 Core

column.append(grid[r][c])

Append the element at row r and column c to the column list.

Collecting elements in order is critical to form an accurate tuple representing the column for equality checks.

Line 21 Core

return count

Return the total count of equal row-column pairs.

Returning the accumulated count completes the solution, providing the final answer as required by the problem.

Line 7 Standard

for row in grid:

Iterate over each row in the grid.

Processing each row individually allows conversion into a tuple and frequency counting, which is the foundation for efficient matching.

Line 13 Standard

for c in range(n):

Iterate over each column index from 0 to n-1.

Column-wise iteration is necessary to build each column tuple for comparison against the row frequency map.

Line 15 Standard

for r in range(n):

Iterate over each row index to collect column elements.

Row-wise iteration within the column loop extracts each element of the column in order, preserving the correct sequence.

Line 3 Standard

n = len(grid)

Calculate the size n of the square grid.

Knowing the dimension n is essential for iterating over rows and columns uniformly, as the grid is guaranteed to be n x n.

Line 14 Standard

column = []

Initialize a list to collect elements of the current column.

This temporary list gathers all elements from the current column before converting to a tuple for lookup.

Line 11 Standard

count = 0

Initialize the counter for equal row-column pairs.

This accumulator will sum the total number of matching pairs found during column processing.

Test Your Understanding

Why is it more efficient to use a hash map of row tuples rather than comparing each row to each column directly?

Because direct comparison requires O(n) element-wise checks for each of the n^2 row-column pairs, resulting in O(n^3) time. Using a hash map with tuple keys reduces equality checks to O(1) average time, lowering total complexity to O(n^2).

Don't just read it. Drill it.

Reconstruct Equal Row and Column Pairs from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Equal Row and Column Pairs drill

or drill a free problem

1	`class Solution:`
2	`def equalPairs(self, grid: List[List[int]]) -> int:`
3	`n = len(grid)`
4
5	`row_count = {}`
6
7	`for row in grid:`
8	`key = tuple(row)`
9	`row_count[key] = row_count.get(key, 0) + 1`
10
11	`count = 0`
12
13	`for c in range(n):`
14	`column = []`
15	`for r in range(n):`
16	`column.append(grid[r][c])`
17
18	`column = tuple(column)`
19	`count += row_count.get(column, 0)`
20
21	`return count`

3	`n = len(grid)`
5	`row_count = {}`
7	`for row in grid:`
8	`key = tuple(row)`
9	`row_count[key] = row_count.get(key, 0) + 1`

Problem

Example

Approach

Solution

Step-by-Step Solution

Build Frequency Map of Rows as Tuples

Construct Column Tuples and Accumulate Matching Counts

Return the Total Count of Equal Row-Column Pairs

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.