{x}
blog image

Equal Row and Column Pairs

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

Solution Explanation:

The problem asks to find the number of pairs (ri, cj) where row ri and column cj are identical in a given square matrix grid. "Identical" means the elements in the row and column are the same and in the same order.

The solution uses a straightforward simulation approach:

  1. Iterate through all possible row-column pairs: The code uses nested loops to iterate through every possible combination of row index i and column index j in the grid.

  2. Compare row and column: For each pair (i, j), it compares the elements of row i and column j. It does this using another inner loop (k loop). If any element in row i differs from the corresponding element in column j, the flag ok is set to 0, indicating they are not equal.

  3. Count equal pairs: If, after checking all elements, ok remains 1, it means row i and column j are equal, and the ans (answer) counter is incremented.

  4. Return the count: Finally, the function returns the value of ans, which represents the total number of equal row-column pairs found.

Time and Space Complexity Analysis

  • Time Complexity: The code has three nested loops, each running up to n times (where n is the dimension of the square matrix). Therefore, the time complexity is O(n³). This is because for every row-column pair, we need to compare n elements.

  • Space Complexity: The algorithm uses only a few variables to store the counters and flags (ans, ok, i, j, k). The space used is constant regardless of the input size. Thus, the space complexity is O(1).

Code Examples in Different Languages

The code examples provided demonstrate the solution's implementation in Python, Java, C++, Go, and TypeScript. They all follow the same basic logic described above, with minor syntactic differences. The core nested loop structure remains the same across all languages.