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].length
- 1 <= n <= 200
- 1 <= grid[i][j] <= 105
Implementations and explanation
Python (naive)
class Solution:
def equalPairs(self, grid: List[List[int]]) -> int:
if not len(grid):
return 0
if len(grid) == 1:
return 1
count = 0
for row in grid:
for c in range(len(grid)):
col = []
for r in range(len(grid)):
col.append(grid[r][c])
if row == col:
count += 1
return count
grid = [[3, 2, 1],
[1, 7, 6],
[2, 7, 7]]
Rows:
[3, 2, 1]
[1, 7, 6]
[2, 7, 7]
Columns:
[3, 1, 2]
[2, 7, 7]
[1, 6, 7]
The code will check if any row is exactly the same as any column. In this example the second row [1,7,6] is not the same as any column. But the third row [2,7,7] is the same as the second column [2,7,7].
Breaking Down the Code:
If the grid is empty, there are no matches.
if not len(grid): return 0
🐍Think of it as: “If there’s no game board, we can’t play, so there are zero matches.”
If the grid has only one row, there is one match.
if len(grid) == 1: return 1
🐍If you only have one row, it will match the only column.
Let’s count the matches.
count = 0
🐍We start with a score of zero.
Look at each row, one by one.
for row in grid:
🐍We’re going to go through each line of numbers (each row) on the board.
For each row, look at each column, one by one.
for c in range(len(grid)):
🐍For every row, we’re going to check all the columns.
Make a column.
col = []
for r in range(len(grid)): col.append(grid[r][c])
🐍To check if a row matches a column, we need to take all the numbers from the top to the bottom of that column and put them in a list.
Is the row the same as the column?
if row == col: count += 1
🐍If the row’s numbers are exactly the same as the column’s numbers in the same order, we add one to our score.
Tell us the total number of matches.
return count
🐍After checking all the rows and columns, we tell you how many times a row matched a column.
Python (efficient)
class Solution:
def equalPairs(self, grid: List[List[int]]) -> int:
n = len(grid)
row_counts = {}
col_counts = {}
# Count row occurrences
for row in grid:
row_tuple = tuple(row) # Convert list to tuple for hashability
row_counts[row_tuple] = row_counts.get(row_tuple, 0) + 1
# Count column occurrences
for c in range(n):
col = tuple(grid[r][c] for r in range(n))
col_counts[col] = col_counts.get(col, 0) + 1
# Count matching pairs
count = 0
for row_tuple, row_count in row_counts.items():
if row_tuple in col_counts:
count += row_count * col_counts[row_tuple]
return count
Let’s use our example again:
grid = [[3, 2, 1],
[1, 7, 6],
[2, 7, 7]]
Let’s count the rows.
row_counts = {}
🐍Think of this as an empty box where we’ll put the rows and how many of each type we have.
Let’s turn the rows into special lists that we can count.
row_tuple = tuple(row)
🐍Imagine we take each row of socks and tie them together so we can easily tell if they are the same as another tied group of socks.
Count how many of each row we have.
row_counts[row_tuple] = row_counts.get(row_tuple, 0) + 1
🐍We look at each tied group of socks (each row) and say, “We have one of these!” If we see the same tied group again, we say, “We have two of these!”
Let’s count the columns.
col_counts = {}
🐍We have another empty box for the columns.
Let’s turn the columns into special lists that we can count.
col = tuple(grid[r][c] for r in range(n))
🐍We do the same thing for the columns, tying the socks together.
Count how many of each column we have.
col_counts[col] = col_counts.get(col, 0) + 1
🐍We count how many of each tied group of column socks we have.
Let’s find the matching pairs.
count = 0
🐍We start with zero matches.
Look at each row and see if it has a matching column.
for row_tuple, row_count in row_counts.items():
🐍We go through each tied group of row socks.
If the row has a matching column, count the pairs.
if row_tuple in col_counts: count += row_count * col_counts[row_tuple]
🐍If we find a tied group of column socks that is exactly the same as the tied group of row socks, we multiply the number of row groups by the number of column groups and add it to our match count.
Tell us how many matching pairs we found.
return count
🐍We tell you the total number of perfectly matching sock groups.
Typescript
function equalPairs(grid: number[][]): number {
const n = grid.length;
const rowCounts: { [key: string]: number } = {};
const colCounts: { [key: string]: number } = {};
// Count row occurrences
for (const row of grid) {
const rowTuple = row.join(','); // Convert array to string for hashability
rowCounts[rowTuple] = (rowCounts[rowTuple] || 0) + 1;
}
// Count column occurrences
for (let c = 0; c < n; c++) {
const col: number[] = [];
for (let r = 0; r < n; r++) {
col.push(grid[r][c]);
}
const colTuple = col.join(','); // Convert array to string for hashability
colCounts[colTuple] = (colCounts[colTuple] || 0) + 1;
}
// Count matching pairs
let count = 0;
for (const rowTuple in rowCounts) {
if (colCounts.hasOwnProperty(rowTuple)) {
count += rowCounts[rowTuple] * colCounts[rowTuple];
}
}
return count;
}
Look at the Rows
🟡First, we go through each row of the grid.
🟡We turn each row into a special string (like a secret code) so we can remember it. For example, if a row is [1, 2, 3], the secret code is "1,2,3".
🟡We count how many times we see each secret code. If we see "1,2,3" twice, we remember that.
Look at the Columns
🟡Now, we do the same thing for the columns.
🟡We turn each column into a secret code.
🟡We count how many times we see each column’s secret code.
Find the Matches
🟡We look at all the row secret codes.
🟡For each row code, we check if we saw the same secret code in the columns.
🟡If we find a match, that means a row is exactly the same as a column!
🟡If a row appears twice, and the same column appears 3 times, there are 2 * 3 = 6 matches.
🟡We add up all the matches to get the final answer.
Why do we use secret codes (strings)?
🟡Computers are good at comparing strings. It’s like comparing words.
🟡It’s harder for computers to directly compare lists of numbers, especially to use them as keys in a count.
🟡Using the string allows us to use an object like a counter, since objects use strings as keys.
Go
import "fmt"
func arrayToString(arr []int) string {
str := ""
for _, num := range arr {
str += fmt.Sprintf("%d,", num)
}
return str
}
func equalPairs(grid [][]int) int {
n := len(grid)
rowCounts := make(map[string]int)
colCounts := make(map[string]int)
// Count row occurrences
for _, row := range grid {
rowStr := arrayToString(row)
rowCounts[rowStr]++
}
// Count column occurrences
for c := 0; c < n; c++ {
col := make([]int, n)
for r := 0; r < n; r++ {
col[r] = grid[r][c]
}
colStr := arrayToString(col)
colCounts[colStr]++
}
// Count matching pairs
count := 0
for rowStr, rowCount := range rowCounts {
if colCount, ok := colCounts[rowStr]; ok {
count += rowCount * colCount
}
}
return count
}
Make the rows into words (arrayToString):
🔵The arrayToString function takes a list of numbers (a row or column) and turns it into a "word" by putting all the numbers together with commas in between.
🔵For example, the row [1, 2, 3] becomes the word "1,2,3,".
Count how many times each row appears (rowCounts):
🔵The equalPairs function looks at each row in the grid.
🔵It uses the “word” version of the row (from step 1).
🔵It keeps track of how many times each “word” appears. If the row [1,2,3] appears twice, the program remembers that.
Count how many times each column appears (colCounts):
🔵The code then does the same thing for the columns.
🔵It takes each column, turns it into a “word”, and counts how many times each “word” appears.
Find matching rows and columns (matching pairs):
🔵Now, the program compares the “words” from the rows and the “words” from the columns.
🔵If a row “word” is the same as a column “word”, it means that row and that column are the same!
🔵If a row appears 2 times and a column appears 3 times, and they are the same, that means that there are 2 * 3 = 6 matching pairs.
🔵It adds up all the matching pairs.
Tell you the total number of matches (count):
🔵Finally, the program tells you the total number of times a row and a column were the same.
If you liked this content I’d appreciate an upvote or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.
Muchas gracias!
Follow me for more content like this.
X | PeakD | Rumble | YouTube | Linked In | GitHub | PayPal.me | Medium
Down below you can find other ways to tip my work.
BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"