Equal Row and Column Pairs - Solution & Explanation

Q: Is Equal Row and Column Pairs easy or hard?

Equal Row and Column Pairs is classified as a Medium problem on LeetCode. The brute-force solution is straightforward, but identifying the hashing optimization that reduces comparisons from O(n^3) to O(n^2) is the key insight.

Q: Equal Row and Column Pairs Python/Java solution

In Python, rows and columns are typically converted into tuples and stored in a dictionary or Counter. In Java, arrays or lists can be serialized into strings or stored using List objects in a HashMap. Both implementations follow the same hashing strategy with O(n^2) time complexity.

Q: How to solve Equal Row and Column Pairs in O(n^2)?

Convert each row of the grid into a tuple and store it in a dictionary with its count. Then build each column as a tuple and check if it exists in the dictionary. If it does, add the stored frequency to the result. Building rows and columns each requires O(n^2) work, resulting in an overall O(n^2) solution.

Q: What is the best approach for Equal Row and Column Pairs?

The most efficient approach uses hashing with a dictionary. Store every row of the matrix as a tuple in a hash map with its frequency. Then construct each column as a tuple and check how many times it appears in the map. This reduces the complexity from O(n^3) brute force to O(n^2) with O(n^2) additional space.

Q: Is Equal Row and Column Pairs asked at Google/Amazon/Meta?

Matrix hashing and row-column comparison problems appear frequently in interviews at large tech companies including Amazon, Google, and Meta. Variants that require recognizing repeating patterns in rows or columns are common in data structure and algorithm interview rounds.

Q: What data structure is used in Equal Row and Column Pairs?

The optimal solution relies on a hash table (dictionary or unordered_map). Each row is converted into a hashable sequence such as a tuple or string and stored with its frequency. Columns are constructed in the same format and checked against the map for matches.

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

The brute-force iterative comparison takes O(n^3) time because every row is compared with every column and each comparison checks n elements. The optimized hashing approach reduces the complexity to O(n^2) by storing row signatures in a dictionary and performing constant-time lookups for each column.

MediumArray Hash Table Matrix Simulation15 min readAsked at: Amazon, Microsoft, Meta +3

Practice this problem

Problem Statement

Given a 0-indexed n x n integer matrix grid, return the number of pairs (r_i, c_j) such that row r_i and column c_j 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:

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:

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] <= 10⁵

Approach Overview

Problem Overview: You receive an n x n grid. The task is to count how many pairs (ri, cj) exist such that the entire i-th row is identical to the j-th column. Every element must match in order, not just as a set.

Approach 1: Iterative Comparison Approach (O(n^3) time, O(1) space)

The straightforward strategy compares every row with every column. For each row i, iterate through every column j. Then check if grid[i][k] == grid[k][j] for all k from 0 to n-1. If all elements match, increment the count. This works because each row and column can be treated as sequences of length n. The drawback is the nested iteration: n rows × n columns × n element comparisons, giving O(n^3) time. Space stays O(1) since the comparison happens directly on the grid without additional storage. This approach is simple and helps verify correctness before optimizing.

Approach 2: Hashing with Dictionary (O(n^2) time, O(n^2) space)

The key observation: rows and columns are sequences that can be hashed. First, convert every row into a hashable structure such as a tuple and store its frequency in a dictionary. Next, build each column as a tuple and check if it exists in the dictionary. If it does, add the stored frequency to the answer. This works because identical sequences produce identical keys, allowing constant-time lookups. Constructing all rows takes O(n^2), constructing all columns takes another O(n^2), and each lookup is O(1). The result is an overall O(n^2) time complexity with O(n^2) space for storing row signatures. This approach leverages concepts from hash tables and structured traversal of a matrix.

Representing rows and columns as tuples ensures order-sensitive comparison. This matters because [1,2,3] must not match [3,2,1]. Languages without native tuple hashing can serialize rows into strings or arrays before inserting them into the map.

Recommended for interviews: The hashing approach is the expected solution. Interviewers want to see that you recognize repeated sequence comparisons and replace them with hash lookups. Explaining the brute-force comparison first demonstrates understanding of the problem, then transitioning to a dictionary-based optimization shows strong problem-solving skills. The pattern appears often in array and grid problems where rows or columns act as comparable signatures.

Approach 1: Iterative Comparison Approach

The straightforward way to solve the problem is by iteratively comparing each row with every column to determine if they are equal. This approach requires looping through each pair of row and column and verifying the elements one by one.

This C code iterates over each row and column pair and compares their elements. If a pair matches, it increments the count. The algorithm first checks each row against every column using two nested loops and a third loop for element-wise comparison.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^3), as it involves comparing elements for each pair. Space Complexity: O(1), since no extra data structures are used except for counters.

Try this approach in the editor →

Approach 2: Hashing with Dictionary

By converting rows and columns into hashable objects (such as tuples in Python or strings in other languages), we can store their occurrences in a dictionary or a hash map. This facilitates a more efficient comparison by checking the presence of corresponding row and column hashes in the stored data structure.

By transposing the matrix first, each row in the original matrix can be compared directly with the columns of the transposed matrix. A helper function is used to compare arrays element by element.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2) for transposing and additional O(n^3) for comparisons. Space Complexity: O(n^2) for storing the transposed matrix.

Try this approach in the editor →

Approach 3: Simulation

We directly compare each row and column of the matrix grid. If they are equal, then it is a pair of equal row-column pairs, and we increment the answer by one.

The time complexity is O(n^3), where n is the number of rows or columns in the matrix grid. The space complexity is O(1).

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Iterative Comparison Approach	Time Complexity: O(n^3), as it involves comparing elements for each pair. Space Complexity: O(1), since no extra data structures are used except for counters.
Hashing with Dictionary	Time Complexity: O(n^2) for transposing and additional O(n^3) for comparisons. Space Complexity: O(n^2) for storing the transposed matrix.
Simulation	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Iterative Comparison	O(n^3)	O(1)	Useful as a baseline solution or when constraints are very small
Hashing with Dictionary	O(n^2)	O(n^2)	Best general solution; converts rows and columns to hashable keys for fast lookups

Video Solution

Equal Row and Column Pairs | Leetcode-2352 | Google, Microsoft | Explanation ➕ Live Coding • codestorywithMIK • 10,493 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Equal Row and Column Pairs easy or hard?

Equal Row and Column Pairs is classified as a Medium problem on LeetCode. The brute-force solution is straightforward, but identifying the hashing optimization that reduces comparisons from O(n^3) to O(n^2) is the key insight.

Equal Row and Column Pairs Python/Java solution

In Python, rows and columns are typically converted into tuples and stored in a dictionary or Counter. In Java, arrays or lists can be serialized into strings or stored using List objects in a HashMap. Both implementations follow the same hashing strategy with O(n^2) time complexity.

How to solve Equal Row and Column Pairs in O(n^2)?

Convert each row of the grid into a tuple and store it in a dictionary with its count. Then build each column as a tuple and check if it exists in the dictionary. If it does, add the stored frequency to the result. Building rows and columns each requires O(n^2) work, resulting in an overall O(n^2) solution.

What is the best approach for Equal Row and Column Pairs?

The most efficient approach uses hashing with a dictionary. Store every row of the matrix as a tuple in a hash map with its frequency. Then construct each column as a tuple and check how many times it appears in the map. This reduces the complexity from O(n^3) brute force to O(n^2) with O(n^2) additional space.

Is Equal Row and Column Pairs asked at Google/Amazon/Meta?

Matrix hashing and row-column comparison problems appear frequently in interviews at large tech companies including Amazon, Google, and Meta. Variants that require recognizing repeating patterns in rows or columns are common in data structure and algorithm interview rounds.

What data structure is used in Equal Row and Column Pairs?

The optimal solution relies on a hash table (dictionary or unordered_map). Each row is converted into a hashable sequence such as a tuple or string and stored with its frequency. Columns are constructed in the same format and checked against the map for matches.

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

The brute-force iterative comparison takes O(n^3) time because every row is compared with every column and each comparison checks n elements. The optimized hashing approach reduces the complexity to O(n^2) by storing row signatures in a dictionary and performing constant-time lookups for each column.

Ready to solve this problem?

Practice Equal Row and Column Pairs with our built-in code editor and test cases.

Practice on FleetCode

Delete Greatest Value in Each Row

Problem Info

DifficultyMedium

Acceptance70.9%

Approaches3

Reading time15 min

Asked at

Amazon Microsoft Meta Google Bloomberg

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Iterative Comparison Approach

Code

Complexity

Approach 2: Hashing with Dictionary

Code

Complexity

Approach 3: Simulation

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents