We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Equal Row and Column Pairs

Number: 2428

Difficulty: Medium

Paid? No

Companies: Google, Apple, Adobe, Amazon, Microsoft, DE Shaw

Problem Description

Given an n x n matrix grid, count the number of pairs (r_i, c_j) such that the ith row and jth column are identical (contain the same elements in the same order).

Key Insights

  • Use a hash table (dictionary) to store the frequency of each row (after converting the row to an immutable and comparable type, such as a tuple).
  • For each column, form the column as a sequence and check if this sequence exists in the row hash table.
  • The total count is the sum over all columns of the frequency of the matching row pattern.

Space and Time Complexity

Time Complexity: O(n^2) – iterating over all rows and then over all columns. Space Complexity: O(n^2) – storing up to n rows (each of length n) in the hash table.

Solution

The approach involves two main steps:

  1. Iterate over each row in the grid, convert the row into a tuple (or any immutable representation), and store its frequency in a hash table.
  2. For each column, build a tuple representing the column values from top to bottom, and check if this column tuple exists in the hash table. If it exists, add its frequency to the answer. This method is efficient because both the row and column extraction require O(n^2) operations in total and the hash table operations are O(1) on average.

Code Solutions

# Python solution
def equalPairs(grid):
    n = len(grid)
    # Create a dictionary to count the frequency of each row (as tuple)
    row_count = {}
    for row in grid:
        row_tuple = tuple(row)
        row_count[row_tuple] = row_count.get(row_tuple, 0) + 1

    result = 0
    # For each column, build the tuple and add the frequency from row_count if it exists
    for j in range(n):
        col = tuple(grid[i][j] for i in range(n))
        result += row_count.get(col, 0)
    return result

# Example usage:
grid = [[3,2,1],[1,7,6],[2,7,7]]
print(equalPairs(grid))  # Output: 1
← Back to All Questions