Problem Description

You are given a square matrix grid of size n x n containing integers. Your task is to count how many pairs of rows and columns are equal to each other.

A row-column pair (ri, cj) consists of:

• Row ri: the i-th row of the matrix
• Column cj: the j-th column of the matrix

A row and a column are considered equal if they have the exact same elements in the exact same order. For example, if row 2 is [1, 2, 3] and column 0 is [1, 2, 3], they form an equal pair.

The solution iterates through all possible row-column combinations. For each pair (i, j), it checks if row i matches column j by comparing element by element. Specifically, it verifies that grid[i][0] equals grid[0][j], grid[i][1] equals grid[1][j], and so on for all n elements. If all elements match in order, the counter is incremented.

The time complexity is O(n³) since we check n² pairs and each comparison takes O(n) time to verify all elements.

Intuition

The key insight is recognizing that we need to compare sequences of elements. Since we're working with a square matrix, every row has exactly n elements and every column also has exactly n elements, making them directly comparable.

To check if a row and column are equal, we need to verify that their elements match position by position. For row i and column j to be equal:

• The first element of row i (which is grid[i][0]) must equal the first element of column j (which is grid[0][j])
• The second element of row i (which is grid[i][1]) must equal the second element of column j (which is grid[1][j])
• And so on for all n positions

This pattern reveals that for the k-th position, we're comparing grid[i][k] with grid[k][j]. Notice how the row index stays constant at i while we vary the column index k, and for the column, the column index stays constant at j while we vary the row index k.

The brute force approach naturally emerges: try every possible row-column pair. Since we have n rows and n columns, we have n² total pairs to check. For each pair, we perform an element-by-element comparison. The all() function elegantly handles this by checking if all elements at corresponding positions are equal, returning True only when the entire row matches the entire column.

Solution Approach

The solution uses a straightforward simulation approach with nested loops to check all possible row-column pairs.

Implementation Steps:

1. Initialize the counter: Start with ans = 0 to keep track of equal row-column pairs.

2. Iterate through all pairs: Use two nested loops where i represents the row index (from 0 to n-1) and j represents the column index (from 0 to n-1). This generates all n² possible (ri, cj) pairs.

3. Compare row i with column j: For each pair (i, j), we need to check if row i equals column j. This is done using:

   all(grid[i][k] == grid[k][j] for k in range(n))

   This generator expression checks each position k from 0 to n-1:

   • grid[i][k] gives us the k-th element of row i
   • grid[k][j] gives us the k-th element of column j
   • The all() function returns True only if every comparison is True

4. Count matches: When all() returns True, it means row i and column j are equal. In Python, True is treated as 1 and False as 0, so we can directly add the result to our answer:

   ans += all(grid[i][k] == grid[k][j] for k in range(n))

5. Return the result: After checking all n² pairs, return the total count.

The algorithm doesn't require any additional data structures beyond the input matrix. The space complexity is O(1) (excluding the input), and the time complexity is O(n³) - we have n² pairs to check, and each comparison takes O(n) time.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider the following 3×3 matrix:

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

We need to find all row-column pairs where the row and column have identical elements in the same order.

Step 1: Initialize counter

• ans = 0
• n = 3 (matrix size)

Step 2: Check all row-column pairs

Let's examine each pair (i, j):

Pair (0, 0): Compare row 0 [3, 2, 1] with column 0 [3, 1, 2]

• Position 0: grid[0][0] = 3 vs grid[0][0] = 3 ✓
• Position 1: grid[0][1] = 2 vs grid[1][0] = 1 ✗
• Not equal, move on

Pair (0, 1): Compare row 0 [3, 2, 1] with column 1 [2, 7, 7]

• Position 0: grid[0][0] = 3 vs grid[0][1] = 2 ✗
• Not equal, move on

Pair (0, 2): Compare row 0 [3, 2, 1] with column 2 [1, 6, 7]

• Position 0: grid[0][0] = 3 vs grid[0][2] = 1 ✗
• Not equal, move on

Pair (1, 0): Compare row 1 [1, 7, 6] with column 0 [3, 1, 2]

• Position 0: grid[1][0] = 1 vs grid[0][0] = 3 ✗
• Not equal, move on

Pair (1, 1): Compare row 1 [1, 7, 6] with column 1 [2, 7, 7]

• Position 0: grid[1][0] = 1 vs grid[0][1] = 2 ✗
• Not equal, move on

Pair (1, 2): Compare row 1 [1, 7, 6] with column 2 [1, 6, 7]

• Position 0: grid[1][0] = 1 vs grid[0][2] = 1 ✓
• Position 1: grid[1][1] = 7 vs grid[1][2] = 6 ✗
• Not equal, move on

Pair (2, 0): Compare row 2 [2, 7, 7] with column 0 [3, 1, 2]

• Position 0: grid[2][0] = 2 vs grid[0][0] = 3 ✗
• Not equal, move on

Pair (2, 1): Compare row 2 [2, 7, 7] with column 1 [2, 7, 7]

• Position 0: grid[2][0] = 2 vs grid[0][1] = 2 ✓
• Position 1: grid[2][1] = 7 vs grid[1][1] = 7 ✓
• Position 2: grid[2][2] = 7 vs grid[2][1] = 7 ✓
• Match found! ans = 1

Pair (2, 2): Compare row 2 [2, 7, 7] with column 2 [1, 6, 7]

• Position 0: grid[2][0] = 2 vs grid[0][2] = 1 ✗
• Not equal, move on

Step 3: Return result

• Total equal pairs found: 1

The only equal row-column pair is (row 2, column 1), both containing [2, 7, 7].

Solution Implementation

Time and Space Complexity

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

• The outer two loops iterate through all pairs of (i, j) positions, contributing O(n^2) iterations
• For each pair, the all() function with the generator expression checks n elements by comparing grid[i][k] with grid[k][j] for all k from 0 to n-1, contributing O(n) operations
• Therefore, the total time complexity is O(n^2) × O(n) = O(n^3)

The space complexity is O(1). The algorithm only uses a constant amount of extra space for variables n, ans, i, j, and the iterator k in the generator expression. The generator expression itself doesn't create any additional data structures and evaluates lazily, using constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing Row-Column Indexing

A frequent mistake is mixing up how to access row elements versus column elements. When comparing row i with column j, developers often write:

• Wrong: grid[k][i] for row elements or grid[j][k] for column elements
• Correct: grid[i][k] for the k-th element of row i and grid[k][j] for the k-th element of column j

Solution: Remember that in a 2D array grid[row][col], the first index is always the row. So for row i, iterate through columns with grid[i][k], and for column j, iterate through rows with grid[k][j].

2. Inefficient String/Tuple Comparison Approach

Some developers convert rows and columns to strings or tuples for comparison:

# Inefficient approach
for i in range(n):
    row = str(grid[i])  # or tuple(grid[i])
    for j in range(n):
        col = str([grid[k][j] for k in range(n)])
        if row == col:
            pair_count += 1

This creates unnecessary objects and can be slower, especially with large matrices.

Solution: Stick with element-by-element comparison using the generator expression with all(). It's more memory-efficient and stops early if a mismatch is found.

3. Not Handling Edge Cases

Forgetting to consider:

• Empty grid (n = 0)
• Single element grid (n = 1)
• Grids with duplicate values that might cause counting errors

Solution: The current implementation naturally handles these cases, but always verify:

• A 1×1 grid correctly returns 1 (the single row equals the single column)
• Empty grids are typically not given in this problem, but checking if not grid at the start can prevent errors

4. Attempting Optimization with Hashing Without Considering Order

Some might try to optimize by hashing rows and columns:

# Wrong optimization attempt
row_set = {frozenset(row) for row in grid}
col_set = {frozenset(grid[k][j] for k in range(n)) for j in range(n)}

This fails because sets don't preserve order, and the problem requires exact order matching.

Solution: If optimizing with hashing, use tuples instead of sets to preserve order:

from collections import Counter
n = len(grid)
rows = Counter(tuple(row) for row in grid)
cols = Counter(tuple(grid[i][j] for i in range(n)) for j in range(n))
return sum(rows[key] * cols[key] for key in rows if key in cols)