Leetcode 2352: Equal Row and Column Pairs

Input: The input consists of an n x n matrix of integers, where n is the number of rows and columns.

Example: Input: grid = [[5, 3, 2], [3, 7, 6], [2, 7, 7]]

Constraints:

• 1 <= n <= 200

• 1 <= grid[i][j] <= 10^5

Output: Return the number of pairs of rows and columns that are equal.

Example: Output: 1

Constraints:

• The grid contains only integers and is square.

Goal: The goal is to iterate over rows and columns and check if they match.

Steps:

• For each row, create a column vector corresponding to each column in the grid.

• Compare the row and column vectors. If they are equal, increment the counter.

Goal: The solution should handle grids where n is up to 200 efficiently.

Steps:

• The grid is square with dimensions n x n.

• 1 <= n <= 200.

Assumptions:

• The grid is non-empty and contains integers only.

• The grid contains at least one pair of equal row-column matches.

• Input: Input: grid = [[5, 3, 2], [3, 7, 6], [2, 7, 7]]

• Explanation: The only equal pair is the third row and the second column, both [2, 7, 7].

Approach: To solve the problem, we need to compare rows and columns one by one and count the matching pairs.

Observations:

• This is a straightforward comparison problem where we need to check each row against each column.

• We can use a simple approach where we iterate over the grid and check if each row matches each column.

Steps:

• Iterate through all rows in the grid.

• For each row, compare it with every column of the grid.

• If the row and column match, increment the result counter.

Empty Inputs:

• There will always be at least one matching pair.

Large Inputs:

• The solution should handle grids up to the size of 200 x 200 efficiently.

Special Values:

• If the grid has repeated rows or columns, they should be counted as separate matching pairs.

Constraints:

• The solution should work within the given constraints efficiently.

int equalPairs(vector<vector<int>>& grid) {
    int n = grid.size();
    int ans = 0;
    for (int c = 0; c < n; c++) {
        vector<int> col;
        col.reserve(n);
        for(int i = 0; i < n; i++)
        col.push_back(grid[i][c]);
        ans += count(begin(grid), end(grid), col);
    }
    return ans;
}

1 : Function Declaration

int equalPairs(vector<vector<int>>& grid) {

The function `equalPairs` is declared, which accepts a 2D grid and returns an integer representing the count of identical row-column pairs.

2 : Grid Size Calculation

    int n = grid.size();

The variable `n` is initialized to the size of the grid (number of rows or columns, assuming the grid is square).

3 : Answer Initialization

    int ans = 0;

The variable `ans` is initialized to 0, which will hold the count of identical row-column pairs.

4 : Column Loop Start

    for (int c = 0; c < n; c++) {

A loop is started to iterate over each column `c` in the grid.

5 : Column Vector Declaration

        vector<int> col;

A temporary vector `col` is declared to hold the current column's values as a separate array.

6 : Reserve Space for Column

        col.reserve(n);

The `reserve` function is called on the vector `col` to allocate memory for `n` elements, optimizing the vector's performance.

7 : Row Loop Start

        for(int i = 0; i < n; i++)

A loop is started to iterate over each row `i` in the grid to extract the column values.

8 : Push Column Values

        col.push_back(grid[i][c]);

The value from row `i` and column `c` is pushed into the vector `col`.

9 : Count Matching Rows

        ans += count(begin(grid), end(grid), col);

The `count` function is used to count how many rows in the grid match the current column `col`. The result is added to `ans`.

10 : Return Result

    return ans;

The function returns the total count of row-column pairs that match.

Best Case: O(n^2)

Average Case: O(n^2)

Worst Case: O(n^2)

Description: The time complexity is O(n^2) as we compare each row to each column.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) as we store a column for each comparison, and the size of each column is n.

Leetcode 2352: Equal Row and Column Pairs

Explore →