Equal Row and Column Pairs in Python – LeetCode75 Explained

by

The Equal Row and Column Pairs problem from LeetCode75 is a matrix-based coding challenge that tests your ability to work with 2D arrays, hashing, and tuple comparisons. This problem is widely asked in interviews to evaluate how well you understand matrix traversal and efficient lookups.

Equal Row and Column Pairs in Python – LeetCode75 Explained

In this blog, we’ll break down the problem, walk through examples, and provide a step-by-step Python solution.

Problem Statement

You are given a 0-indexed n x n integer matrix grid.

Return the number of pairs (r, c) such that:

  • The row r is equal to the column c (as in, their elements match exactly in order).

Understanding the Problem

  • Each row has n elements.
  • Each column also has n elements.
  • We need to compare rows with columns and count exact matches.

Naive Approach: Compare every row with every column → O(n^3) (too slow).
Efficient Approach: Use hashing with tuples for quick lookups.

Examples

Example 1:

Input:

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

Output:

1

Explanation:

  • Rows: (3,2,1), (1,7,6), (2,7,7)
  • Columns: (3,1,2), (2,7,7), (1,6,7)
  • Only column (2,7,7) matches row (2,7,7).

Example 2:

Input:

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

Output:

3

Explanation:

  • Matching pairs:
    • Row (2,4,2,2) matches column (2,4,2,2) twice.
    • Row (3,1,2,2) matches column (3,1,2,2).

Python Solution – Step by Step

from typing import List
import collections

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        # Step 1: Count each row as a tuple
        counter = collections.Counter()
        for row in grid:
            counter[tuple(row)] += 1
        
        # Step 2: Check each column and count matches
        ans = 0
        n = len(grid)
        for i in range(n):
            col = []
            for j in range(n):
                col.append(grid[j][i])
            ans += counter[tuple(col)]
        
        return ans

Step-by-Step Explanation

Step 1 – Convert Rows to Tuples
Tuples are hashable, so we store each row in a Counter.

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

Step 2 – Build Each Column
For column i, collect all grid[j][i] values → form a tuple.

Step 3 – Check Matches
Use counter[column_tuple] to add how many rows match this column.

Step 4 – Return Result
Return total count of matching row–column pairs.

Why This Solution Works

  • Using tuples makes rows and columns directly comparable.
  • Counter allows O(1) average lookup.
  • We avoid redundant element-by-element comparisons.

Time and Space Complexity

  • Time Complexity: O(n^2) (building rows and columns)
  • Space Complexity: O(n^2) (storing row tuples in counter)

Edge Cases to Consider

InputOutputExplanation
[[1]]1Single element matches itself
[[1,1],[1,1]]4Every row matches every column
[[3,2],[2,3]]0No row matches any column

Real-World Applications

  • Data validation: Matching records row vs. column in relational datasets.
  • Image processing: Checking for symmetrical pixel patterns.
  • Network analysis: Comparing adjacency matrix rows vs. columns for symmetric graphs.

Conclusion

The Equal Row and Column Pairs problem is an excellent example of applying hashing with tuples to reduce complexity from O(n^3) to O(n^2). By converting rows into hashable keys and comparing them with columns, we achieve a clean and efficient solution.

This technique strengthens your understanding of matrices, hashing, and efficient lookups, which are highly valuable in both coding interviews and real-world applications.

Leave a Comment