Equal Row and Column Pairs Solution In C++/Python/java/JS
Equal Row and Column Pairs Problem Description:
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).
Examples:
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]
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⁵
Brute Force Approach
Let’s try to think about this problem like how a beginner might naturally approach it.
We're given a square grid — a 2D matrix — and we're told to count how many pairs of rows and columns in this grid are exactly the same. That means, for any row ri and any column cj, if the elements in ri appear in the same order as those in cj, we consider that a matching pair.
Now, at first glance, there’s nothing too tricky here. The most straightforward idea that might come to your mind is:
“Why not just compare every row with every column and see if they match?”
That’s actually a pretty reasonable brute force way to start. After all, the number of rows and columns is the same n, so we can just check each row one by one, and for each row, loop through every column and check if they’re identical.
As soon as you start thinking like this, another question pops up: how do I compare a row and a column?
That’s an important step to understand clearly — how exactly do we compare a row with a column?
Let’s start with the row. Rows in a 2D grid are very straightforward to work with. Since the grid is stored as a list of lists (or array of arrays), each row is simply a list in itself. So if you're looking at the r-th row, you can access it directly using something like grid[r]. It’s all laid out in one line — you just grab it, and all the elements are right there in order.
But when it comes to columns, things aren’t as direct. The grid isn’t structured in a way that lets you grab a column just by saying grid[c] — because that gives you a row, not a column. A column is made up of one element from each row, specifically the element at the same index in each of those rows. So to construct column c, you have to go through every row and pick the c-th element from it. That’s why we say we’re looping vertically through the grid.
For example, suppose we’re looking at column 1 in the following grid:
To build column 1, we take the second element (index 1) from each row:
- From row 0: 2
- From row 1: 7
- From row 2: 7
So column 1 becomes: [2, 7, 7]
Now let’s say we want to compare this column to row 2, which is also [2, 7, 7]. Here, we’re comparing two lists:
- One is a row that’s already present and easy to access directly
- The other is a column that we had to manually build by pulling elements from each row
To check if they match, we compare them element by element — first element with first, second with second, and so on. If all elements match in order, we’ve found a valid row-column pair.
This concept of comparing one horizontal sequence (row) to one vertical sequence (column) is really the heart of the brute force approach. It feels very natural once you realize that a column isn’t just sitting there — you have to assemble it manually by picking from each row.
So that’s why in the brute force method, inside the nested loops over rows and columns, we need one more loop — to go over every index k and compare grid[r][k] with grid[k][c]. If they’re all equal, that means the row and the column match perfectly.
From here, the natural next step is writing three nested loops: one for picking a row, another for picking a column, and the third to go element by element and compare them. If all elements match at each index, we count that as one valid pair.
So while this brute force method is very intuitive and straightforward — it's the kind of solution that makes sense without needing deep algorithmic insight — it's also quite expensive computationally. You're comparing every row with every column, and within that, comparing up to n elements. That’s where the O(n³) time complexity comes from. Still, as a first attempt or while trying to understand the problem, this method makes a lot of sense and gives us a strong foundation before thinking about optimization.
Let's understand with an example:
Equal Row and Column Pairs Example:
Input: grid = [[3,2,1], [1,7,6], [2,7,7]]
We iterate over each row (r) and each column (c), and for each pair, check if:
grid[r][k] == grid[k][c] for all k from 0 to n-1
- r = 0, check with all columns:
- c = 0 → compare [3,2,1] with [3,1,2] → not matched
- c = 1 → [3,2,1] vs [2,7,7] → not matched
- c = 2 → [3,2,1] vs [1,6,7] → not matched
- r = 1, check with all columns:
- c = 0 → [1,7,6] vs [3,1,2] → not matched
- c = 1 → [1,7,6] vs [2,7,7] → not matched
- c = 2 → [1,7,6] vs [1,6,7] → not matched
- r = 2, check with all columns:
- c = 0 → [2,7,7] vs [3,1,2] → not matched
- c = 1 → [2,7,7] vs [2,7,7] → matched! ✅
- c = 2 → [2,7,7] vs [1,6,7] → not matched
Final count: 1 match
Only row 2 and column 1 are identical. → Answer = 1
Steps to Implement the Solution:
- Initialize a variable count = 0 to keep track of matching row-column pairs.
- Loop over each row index r from 0 to n - 1.
- For each row r, loop over each column index c from 0 to n - 1.
- Compare row r with column c:
- Initialize a boolean flag isEqual = true.
- Loop through all indices k from 0 to n - 1:
- If grid[r][k] != grid[k][c], set isEqual = false and break.
- If isEqual remains true after the inner loop, increment count.
- After all comparisons, return count as the final answer.
Equal Row and Column Pairs Solution
Code Implementation / Leetcode solution of Equal Row and Column Pairs
1. Equal Row and Column Pairs solution in C++ Try on Compiler
class Solution {
public:
int equalPairs(vector<vector<int>>& grid) {
// Get the size of the grid
int n = grid.size();
// Initialize counter for matching pairs
int count = 0;
// Loop through each row
for (int r = 0; r < n; r++) {
// Loop through each column
for (int c = 0; c < n; c++) {
// Flag to check if row r and column c match
bool isEqual = true;
// Compare each element in row r and column c
for (int k = 0; k < n; k++) {
if (grid[r][k] != grid[k][c]) {
// Mismatch found
isEqual = false;
break;
}
}
// If full match, increment the count
if (isEqual) count++;
}
}
// Return total matching row-column pairs
return count;
}
};
2. Equal Row and Column Pairs solution in Java Try on Compiler
class Solution {
public int equalPairs(int[][] grid) {
// Get the size of the grid
int n = grid.length;
// Initialize counter for matching pairs
int count = 0;
// Loop through each row
for (int r = 0; r < n; r++) {
// Loop through each column
for (int c = 0; c < n; c++) {
// Flag to check if row r and column c match
boolean isEqual = true;
// Compare each element in row r and column c
for (int k = 0; k < n; k++) {
if (grid[r][k] != grid[k][c]) {
// Mismatch found
isEqual = false;
break;
}
}
// If full match, increment the count
if (isEqual) count++;
}
}
// Return total matching row-column pairs
return count;
}
}
3. Equal Row and Column Pairs solution in Python Try on Compiler
class Solution:
def equalPairs(self, grid):
# Get the size of the grid
n = len(grid)
# Initialize counter for matching pairs
count = 0
# Loop through each row
for r in range(n):
# Loop through each column
for c in range(n):
# Flag to check if row r and column c match
isEqual = True
# Compare each element in row r and column c
for k in range(n):
if grid[r][k] != grid[k][c]:
# Mismatch found
isEqual = False
break
# If full match, increment the count
if isEqual:
count += 1
# Return total matching row-column pairs
return count
4. Equal Row and Column Pairs solution in Javascript Try on Compiler
var equalPairs = function(grid) {
// Get the size of the grid
let n = grid.length;
// Initialize counter for matching pairs
let count = 0;
// Loop through each row
for (let r = 0; r < n; r++) {
// Loop through each column
for (let c = 0; c < n; c++) {
// Flag to check if row r and column c match
let isEqual = true;
// Compare each element in row r and column c
for (let k = 0; k < n; k++) {
if (grid[r][k] !== grid[k][c]) {
// Mismatch found
isEqual = false;
break;
}
}
// If full match, increment the count
if (isEqual) count++;
}
}
// Return total matching row-column pairs
return count;
};
Equal Row and Column Pairs Complexity Analysis
Time Complexity: O(n³)
Let's analyze the time complexity of the brute force solution we've implemented.
There are two outer loops iterating over all possible row-column pairs, i.e., for each row r and for each column c, we compare them.
For each such pair, we do a comparison of n elements, one-by-one (using index k) to check if the row and column are identical.
- Outer loop over rows: O(n)
- Inner loop over columns: O(n)
- For each row-column pair, comparison takes: O(n)
Total time = O(n) × O(n) × O(n) = O(n³)
Space Complexity: O(n²)
- Auxiliary Space Complexity: O(1)
The extra space used — like the count variable and the loop variables (r, c, k) — are all primitive types and do not depend on the input size.
Therefore, the auxiliary space complexity is O(1). - Total Space Complexity: O(n²)
The input grid is a 2D vector of size n × n, and that's the main data structure we're working with.
We're not creating any additional large data structures — we're just reading from the input.
So, the total space complexity is O(n²) due to the input grid.
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n³), where n is the number of rows (and columns) in the square grid. Given the constraint 1 ≤ n ≤ 200, this means the algorithm could perform up to O(200³) = 8*10⁶ operations in the worst-case scenario.
While O(n³) might sound heavy at first glance, the absolute number of operations (around 8 million) is still well within the acceptable limits for most online judges, including LeetCode, where problems typically allow up to 10⁶ operations per test case.
Therefore, even though this approach isn't optimized and might not scale to much larger n, it is completely acceptable for the given constraints and performs well in practice. In fact, this brute force solution got accepted on LeetCode.
So, while the time complexity doesn't guarantee efficiency for very large grids, it's sufficiently efficient within the given limits and serves as a good starting point before considering optimized solutions.
How to optimize it?
So far, we've tackled the problem by brute force — comparing every row with every column, element by element, and counting the number of exact matches. That gave us a neat and understandable solution with O(n³) time complexity, which works well within the problem’s constraints.
But now let’s take a step back and think — can we somehow avoid this repetitive comparison and make the process more efficient?
Imagine you’re going through each row and thinking:
“If only I already knew how many columns look exactly like this row, I wouldn’t have to scan through all of them every time.”
That’s the spark of the optimization idea!
Equal Row and Column Pairs Algorithm
Let’s say we could somehow record the structure of each row in a way that makes it fast to check if a similar structure appears in the columns. Here's the key observation: rows are already given as arrays, so it's easy to store them.
But columns need to be “assembled” — we’d need to collect the i-th element from each row to construct the i-th column. Once we do that, it becomes just another array — and arrays can be compared!
Now comes the exciting part: what if we used a hash map (or a frequency map) to count how many times each row appears in the grid?
What is a hashmap?
A HashMap (also called unordered_map/map in C++, or dictionary in Python, or object / Map in JavaScript) is a data structure that allows you to store data in key-value pairs, and more importantly — retrieve it super fast (typically in constant time, O(1)).
Then, as we build each column one by one, we simply check how many times this column (as an array) appeared as a row. If we find a match, that means every one of those matching rows forms a valid (row, column) pair with the current column.
For example, suppose row [2, 4, 2, 2] appeared twice in the grid. If we construct a column that looks exactly like [2, 4, 2, 2], then that one column alone contributes 2 valid pairs, one for each matching row. With this logic, you no longer have to go back and forth comparing individual elements — you just count!
So instead of comparing every row-column pair manually, we flip the process: first store the frequency of all rows, then loop through the columns and look them up. This idea trims the time complexity down to O(n²) — much better for larger values of n.
It’s a beautiful example of how stepping back and thinking in terms of hashing and frequency counting can lead to a significant speed-up in problems that involve comparing structured data like arrays.
Let us understand this with a video,
equal-row-and-column-pairs-optimal-approach-animation
Let's understand with an example:
Equal Row and Column Pairs Example:
Absolutely! Here's the same dry run with all backticks replaced by bold formatting:
Input: grid = [[3,1,2,2], [1,4,4,5], [2,4,2,2], [2,4,2,2]]
Step 1: Count the frequency of each row
We create a HashMap freq:
- Row 0 → [3,1,2,2] → freq[[3,1,2,2]] = 1
- Row 1 → [1,4,4,5] → freq[[1,4,4,5]] = 1
- Row 2 → [2,4,2,2] → freq[[2,4,2,2]] = 1
- Row 3 → [2,4,2,2] → freq[[2,4,2,2]] = 2 (appears twice)
Final freq map:
- [3,1,2,2] → 1
- [1,4,4,5] → 1
- [2,4,2,2] → 2
Step 2: Check each column and count matches in freq
We construct each column one by one and check if it exists in freq.
- Column 0 → [3,1,2,2] → found in freq with count = 1 → +1
- Column 1 → [1,4,4,4] → not found → +0
- Column 2 → [2,4,2,2] → found in freq with count = 2 → +2
- Column 3 → [2,5,2,2] → not found → +0
Total matching pairs = 1 + 2 = 3
Output: 3
How to code it up:
- Initialize a frequency map
Use a map<vector<int>, int> to store the count of each unique row. - Count each row
Loop through every row in the grid and increment its count in the map. - Iterate through each column
For each column index i, build a temporary vector col by collecting the i-th element from each row. - Check if the column exists in the map
If the built col vector exists in the frequency map, add its count to the result. - Return the final count
After checking all columns, return the total number of matching (row, column) pairs.
Equal Row and Column Pairs leetcode Solution
Code Implementation / Equal Row and Column Pairs leetcode Solution
1. Equal Row and Column Pairs solution in C++ Try on Compiler
class Solution {
public:
int equalPairs(vector<vector<int>>& grid) {
// Map to store frequency of each row as a vector
map<vector<int>, int> freq;
// Initialize the count of matching pairs
int count = 0;
// Traverse each row in the grid
for (auto row : grid)
// Increment frequency count for the row
freq[row]++;
// Loop through each column index
for (int i = 0; i < grid.size(); i++) {
// Create a vector to represent the current column
vector<int> col;
// Build the column by collecting the i-th element from each row
for (int j = 0; j < grid.size(); j++) {
col.push_back(grid[j][i]);
}
// Add the frequency of this column if it matches any row
count += freq[col];
}
// Return the total number of matching row-column pairs
return count;
}
};
2. Equal Row and Column Pairs solution in Java Try on Compiler
class Solution {
public int equalPairs(int[][] grid) {
// Map to store frequency of each row
Map<List<Integer>, Integer> freq = new HashMap<>();
// Initialize the count of matching pairs
int count = 0;
// Traverse each row and record its frequency
for (int[] row : grid) {
List<Integer> rowList = new ArrayList<>();
for (int num : row) {
rowList.add(num);
}
freq.put(rowList, freq.getOrDefault(rowList, 0) + 1);
}
// Loop through each column index
for (int i = 0; i < grid.length; i++) {
// Create a list to represent the current column
List<Integer> col = new ArrayList<>();
// Build the column from i-th elements of all rows
for (int j = 0; j < grid.length; j++) {
col.add(grid[j][i]);
}
// Add the frequency of this column if it matches any row
count += freq.getOrDefault(col, 0);
}
// Return the total count of matching pairs
return count;
}
}
3. Equal Row and Column Pairs solution in Python Try on Compiler
class Solution:
def equalPairs(self, grid):
# Dictionary to store frequency of each row
freq = defaultdict(int)
# Initialize count of matching pairs
count = 0
# Traverse each row and record frequency
for row in grid:
freq[tuple(row)] += 1
# Loop through each column index
for i in range(len(grid)):
# Build the column by picking i-th elements from each row
col = tuple(grid[j][i] for j in range(len(grid)))
# Add to count if column matches any row
count += freq[col]
# Return total number of equal row-column pairs
return count
4. Equal Row and Column Pairs solution in Javascript Try on Compiler
var equalPairs = function(grid) {
// Map to store frequency of each row as a string key
const freq = new Map();
// Initialize count of matching pairs
let count = 0;
// Traverse each row and store frequency
for (let row of grid) {
const key = row.join(',');
freq.set(key, (freq.get(key) || 0) + 1);
}
// Loop through each column index
for (let i = 0; i < grid.length; i++) {
// Build the column by collecting i-th element from each row
const col = [];
for (let j = 0; j < grid.length; j++) {
col.push(grid[j][i]);
}
// Convert column to string key
const colKey = col.join(',');
// Add the frequency of this column if it matches any row
count += freq.get(colKey) || 0;
}
// Return total number of equal row-column pairs
return count;
};
Equal Row and Column Pairs Complexity Analysis
Time Complexity: O(n²)
The first part of the solution involves looping through each row of the grid and inserting it into a hashmap. Since each row is a vector of length n, inserting it into the map and computing the hash (or performing comparisons for key collisions) takes O(n) time. Since we do this for n rows, the overall time for this part is O(n × n) or O(n²).
In the second part of the solution, we iterate through each column. For each column index, we build a temporary vector col by collecting the i-th element from every row, which takes O(n) time. We then check whether this column vector exists in the hashmap using freq[col], which again takes O(n) time in the worst case due to vector comparison. Since we do this for all n columns, this part also contributes O(n²) to the total time complexity.
Combining both parts, the total time complexity becomes O(n² + n²) = O(n²).
Thus, the time complexity of the optimized solution using a hashmap is O(n²), where n is the size of the grid (since it’s an n × n matrix).
Space Complexity: O(n²)
- Auxiliary Space Complexity: O(1)
The auxiliary space complexity is O(n) because for each column, we build a temporary vector col of size n to compare against the rows stored in the map. Although we discard and rebuild this vector on each iteration, it still requires O(n) space during execution. - Total Space Complexity: O(n²)
The total space complexity is O(n²) because we use a map to store the frequency of each row. In the worst case, all n rows are unique, and each row is a vector of size n, resulting in O(n × n) = O(n²) space used by the map. Additionally, the temporary vectors used to construct the columns also contribute O(n), but this does not increase the overall asymptotic space usage beyond O(n²).
Therefore, the total space complexity is O(n²).
Similar Problems
Working with a matrix often involves handling data in a structured, grid-like format, which is common in problems related to simulation tasks such as shifting rows or modeling real-world scenarios. Sometimes, converting rows or elements into a flat array helps simplify operations or comparisons. Additionally, a hash table can be useful when we need quick lookups or to track frequencies during the simulation process. Combining these tools makes it easier to design efficient and intuitive solutions.
Now that we have successfully tackled this problem, let's try similar problems.
Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.
In one shift operation:
Element at grid[i][j] moves to grid[i][j + 1].
Element at grid[i][n - 1] moves to grid[i + 1][0].
Element at grid[m - 1][n - 1] moves to grid[0][0].
Return the 2D grid after applying shift operation k times.
You are given an m x n integer matrix mat and an integer k. The matrix rows are 0-indexed.
The following proccess happens k times:
Even-indexed rows (0, 2, 4, ...) are cyclically shifted to the left.
Odd-indexed rows (1, 3, 5, ...) are cyclically shifted to the right.
Return true if the final modified matrix after k steps is identical to the original matrix, and false otherwise.