Equal Row and Column Pairs

MEDIUM

Description

Given a 0-indexed n x n integer matrix grid, return the number of pairs (r_i, c_j) such that row r_i and column c_j 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] <= 10⁵

Approaches

Checkout 3 different approaches to solve Equal Row and Column Pairs. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Comparison

This approach directly implements the problem statement by iterating through every possible pair of a row and a column and comparing them element by element. It is the most straightforward but least efficient method.

Algorithm

Initialize a counter count to 0.
Get the size of the grid, n.
Iterate through each row i from 0 to n-1.
Inside this loop, iterate through each column j from 0 to n-1.
For the current pair (row i, column j), check if they are equal by using a third loop.
Iterate k from 0 to n-1.
Compare grid[i][k] (element from row i) with grid[k][j] (element from column j).
If at any point grid[i][k] != grid[k][j], the row and column are not equal. Break the inner loop and move to the next pair.
If the inner comparison loop completes without finding any mismatch, it means the row and column are equal. Increment the count.
After all pairs have been checked, return count.

The brute-force method involves a systematic check of all n*n possible pairs of rows and columns. We use three nested loops. The outer two loops select a row i and a column j. The innermost loop then iterates from k = 0 to n-1 to compare each element of the selected row grid[i][k] with the corresponding element of the selected column grid[k][j]. If all n elements match for a given (i, j) pair, we increment a counter. This process is repeated until all pairs have been checked.

class Solution {
    public int equalPairs(int[][] grid) {
        int n = grid.length;
        int count = 0;
        for (int i = 0; i < n; i++) { // Iterate through rows
            for (int j = 0; j < n; j++) { // Iterate through columns
                boolean isEqual = true;
                for (int k = 0; k < n; k++) { // Compare elements
                    if (grid[i][k] != grid[k][j]) {
                        isEqual = false;
                        break;
                    }
                }
                if (isEqual) {
                    count++;
                }
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n³). There are three nested loops. The outer two loops iterate through all `n*n` row-column pairs, and the inner loop performs `n` comparisons for each pair.Space Complexity: O(1). The algorithm uses only a constant amount of extra space for loop variables and the counter, regardless of the input grid size.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space, making it very memory-efficient.

Cons:

Very inefficient with a cubic time complexity.
Likely to result in a 'Time Limit Exceeded' error on platforms like LeetCode for larger constraints (e.g., n=200).

Code Solutions

Checking out 3 solutions in different languages for Equal Row and Column Pairs. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Equal Row and Column Pairs

Data Structures:

ArrayHash TableMatrix

Companies:

DE Shaw |