Equal Row and Column Pairs solution and explanation
Google
9 more videos on this problem
Equal Row and Column Pairs | Leetcode-2352 | Google, Microsoft | Explanation ➕ Live CodingcodestorywithMIK · 19:59 · 10K views
Leetcode 2352 Equal Row and Column Pairs | Easy Peasy MapsCoding Decoded · 8:07 · 8K views
Equal Row and Column Pairs - Leetcode 2352 - PythonTechError · 5:30 · 6K views
Leetcode 2352. Equal Row and Column Pairs | Weekly Contest 303. | Google Must Do interview QuestionCode with Alisha · 12:26 · 5K views
Equal Row and Column Pairs - LeetCode 2352 - Python #leetcode #leetcode75Deepti Talesra · 9:46 · 5K views
Equal Row and Column Pairs II Hashing II Maps II Arrays II Leetcode 2352Aryan Mittal · 10:56 · 4K views
2352. Equal Row and Column Pairs (Leetcode Medium)Programming Live with Larry · 4:24 · 1K views
Equal Row and Column Pairs | Leetcode 2352Techdose · 12:17 · 1K views
Daily Leetcode #1169: Jun 13, 2023 - 2352. Equal Row and Column PairsProgramming Live with Larry · 5:52 · 638 views
Solving the 'Equal Row and Column Pairs' Problem in Java LeetCode 75 Study PlanCoding with Christian · 9:53 · 504 views
The problem
Given a 0-indexed n x n integer matrix grid, return the number of pairs (ri, cj) such that row ri and column cj 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].length1 <= n <= 2001 <= grid[i][j] <= 105
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.
def equal_pairs(grid):
n = len(grid)
count = 0
for i in range(n):
for j in range(n):
if all(grid[i][k] == grid[k][j] for k in range(n)):
count += 1
return count
grid = [[3, 2, 1], [1, 7, 6], [2, 7, 7]]
print(equal_pairs(grid))public class EqualRowColumn {
public static int equalPairs(int[][] grid) {
int n = grid.length;
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
boolean isEqual = true;
for (int k = 0; k < n; k++) {
if (grid[i][k] != grid[k][j]) {
isEqual = false;
break;
}
}
if (isEqual) count++;
}
}
return count;
}
public static void main(String[] args) {
int[][] grid = {{3, 2, 1}, {1, 7, 6}, {2, 7, 7}};
System.out.println(equalPairs(grid));
}
}#include <iostream>
#include <vector>
using namespace std;
int countEqualPairs(vector<vector<int>>& grid) {
int n = grid.size();
int count = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
bool equal = true;
for (int k = 0; k < n; ++k) {
if (grid[i][k] != grid[k][j]) {
equal = false;
break;
}
}
if (equal) ++count;
}
}
return count;
}
int main() {
vector<vector<int>> grid = {{3, 2, 1}, {1, 7, 6}, {2, 7, 7}};
cout << countEqualPairs(grid) << endl;
return 0;
}function equalPairs(grid) {
const n = grid.length;
let count = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
let isEqual = true;
for (let k = 0; k < n; k++) {
if (grid[i][k] !== grid[k][j]) {
isEqual = false;
break;
}
}
if (isEqual) count++;
}
}
return count;
}
const grid = [[3, 2, 1], [1, 7, 6], [2, 7, 7]];
console.log(equalPairs(grid));#include <stdio.h>
int countEqualPairs(int n, int grid[n][n]) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int match = 1;
for (int k = 0; k < n; k++) {
if (grid[i][k] != grid[k][j]) {
match = 0;
break;
}
}
if (match) count++;
}
}
return count;
}
int main() {
int grid[3][3] = {{3, 2, 1}, {1, 7, 6}, {2, 7, 7}};
int result = countEqualPairs(3, grid);
printf("%d\n", result);
return 0;
}using System;
public class Program {
public static int EqualPairs(int[,] grid) {
int n = grid.GetLength(0);
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
bool isEqual = true;
for (int k = 0; k < n; k++) {
if (grid[i, k] != grid[k, j]) {
isEqual = false;
break;
}
}
if (isEqual) count++;
}
}
return count;
}
public static void Main() {
int[,] grid = { { 3, 2, 1 }, { 1, 7, 6 }, { 2, 7, 7 } };
Console.WriteLine(EqualPairs(grid));
}
}The Python code uses list comprehension to check equality of rows and columns within nested loops, producing the count of equal pairs if elements match one to one.
Time Complexity: O(n^3), considering three levels of iteration for elements evaluation. Space Complexity: O(1) since only a scalar variable is used for counting.
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.
def equal_pairs(grid):
from collections import Counter
n = len(grid)
row_count = Counter(tuple(row) for row in grid)
count = 0
for j in range(n):
col = tuple(grid[i][j] for i in range(n))
count += row_count[col]
return count
grid = [[3, 2, 1], [1, 7, 6], [2, 7, 7]]
print(equal_pairs(grid))import java.util.HashMap;
public class EqualRowColumn {
public static int equalPairs(int[][] grid) {
int n = grid.length;
HashMap<String, Integer> rowMap = new HashMap<>();
for (int i = 0; i < n; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; j++) {
sb.append(grid[i][j]).append(",");
}
String row = sb.toString();
rowMap.put(row, rowMap.getOrDefault(row, 0) + 1);
}
int count = 0;
for (int j = 0; j < n; j++) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append(grid[i][j]).append(",");
}
String col = sb.toString();
count += rowMap.getOrDefault(col, 0);
}
return count;
}
public static void main(String[] args) {
int[][] grid = {{3, 2, 1}, {1, 7, 6}, {2, 7, 7}};
System.out.println(equalPairs(grid));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
typedef vector<int> vi;
int equalPairs(vector<vi>& grid) {
int n = grid.size();
unordered_map<string, int> rowMap;
for (int i = 0; i < n; ++i) {
string key = "";
for (int j = 0; j < n; ++j) {
key += to_string(grid[i][j]) + ",";
}
rowMap[key]++;
}
int count = 0;
for (int j = 0; j < n; ++j) {
string key = "";
for (int i = 0; i < n; ++i) {
key += to_string(grid[i][j]) + ",";
}
if (rowMap.count(key)) {
count += rowMap[key];
}
}
return count;
}
int main() {
vector<vector<int>> grid = {{3, 2, 1}, {1, 7, 6}, {2, 7, 7}};
cout << equalPairs(grid) << endl;
return 0;
}function equalPairs(grid) {
const n = grid.length;
let count = 0;
const rowMap = new Map();
for (let i = 0; i < n; i++) {
const row = grid[i].join(',');
rowMap.set(row, (rowMap.get(row) || 0) + 1);
}
for (let j = 0; j < n; j++) {
const col = Array.from({ length: n }, (_, i) => grid[i][j]).join(',');
count += rowMap.get(col) || 0;
}
return count;
}
const grid = [[3, 2, 1], [1, 7, 6], [2, 7, 7]];
console.log(equalPairs(grid));#include <stdio.h>
#include <string.h>
#define MAX 1000
int compare(int a[], int b[], int n) {
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) return 0;
}
return 1;
}
int equalPairs(int n, int grid[n][n]) {
int count = 0;
int transposed[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
transposed[j][i] = grid[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (compare(grid[i], transposed[j], n)) count++;
}
}
return count;
}
int main() {
int grid[3][3] = {{3, 2, 1}, {1, 7, 6}, {2, 7, 7}};
int result = equalPairs(3, grid);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class EqualRowColumn {
public static int EqualPairs(int[,] grid) {
int n = grid.GetLength(0);
var rowMap = new Dictionary<string, int>();
for (int i = 0; i < n; i++) {
string row = string.Join(",", Enumerable.Range(0, n).Select(j => grid[i, j]));
if (!rowMap.ContainsKey(row))
rowMap[row] = 0;
rowMap[row]++;
}
int count = 0;
for (int j = 0; j < n; j++) {
string col = string.Join(",", Enumerable.Range(0, n).Select(i => grid[i, j]));
if (rowMap.ContainsKey(col)) {
count += rowMap[col];
}
}
return count;
}
public static void Main() {
int[,] grid = { { 3, 2, 1 }, { 1, 7, 6 }, { 2, 7, 7 } };
Console.WriteLine(EqualPairs(grid));
}
}The Python code uses a Counter to hash rows as tuple keys, allowing quick comparison with columns formed as tuples; the count increments with matches based on row-hash frequency.
Time Complexity: O(n^2), managing hash with tuples in row and column comparisons. Space Complexity: O(n^2) for storing unique rows in the Counter.
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).
function equalPairs(grid: number[][]): number {
const n = grid.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
let ok = 1;
for (let k = 0; k < n; ++k) {
if (grid[i][k] !== grid[k][j]) {
ok = 0;
break;
}
}
ans += ok;
}
}
return ans;
}func equalPairs(grid [][]int) (ans int) {
for i := range grid {
for j := range grid {
ok := 1
for k := range grid {
if grid[i][k] != grid[k][j] {
ok = 0
break
}
}
ans += ok
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Comparison Approach | Time Complexity: O(n^3), considering three levels of iteration for elements evaluation. Space Complexity: O(1) since only a scalar variable is used for counting. |
| Hashing with Dictionary | Time Complexity: O(n^2), managing hash with tuples in row and column comparisons. Space Complexity: O(n^2) for storing unique rows in the Counter. |
| Simulation | – |
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 |
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.