< Back





2352. Equal Row and Column Pairs

The description of this problem leaves much to be desired as it's honestly confusing trying to
decipher what the problem wants from us.

Ok. You've got a n x n matrix of numbers. Sometimes the rows and columns have the same sequence of
numbers. We want to find the number of pairs of these rows and columns that have the same sequence of
numbers. We can find the number of pairs by mutliplying the numbers of times we've seen a matching
row and column.

To track the number of times we've seen a row or a column, let's maintain a dictionary. How do we
index into said dictionary for a row or column? We convert the list that defines the row or column
into a tuple. Tuples are hashable - super nice to solve stuff in Python.

There's a trick here. Rows are easy to access. Columns, on the other hand, we're going to have to
rebuild them using i and j to index into the matrix. Just requires a couple of extra lines, don't
freak out.

Alright, once we catalouged all the rows and columns and how many times we've seen them, we compile
our answer. We iterate through all the row tuples we've discovered, pulling the count of the number
of times we've seen a row. We also index into the columns with the same row tuple, pulling the count
for the number of time we've seen that column. Finally, we add their product to the answer.

The solution is as follows:


  class Solution:
      def equalPairs(self, grid: List[List[int]]) -> int:
          ans = 0
          n = len(grid)

          rows = defaultdict(int)
          for row in grid:
              rows[tuple(row)] += 1

          cols = defaultdict(int)
          for j in range(n):
              col = []

              for i in range(n):
                  col.append(grid[i][j])

              cols[tuple(col)] += 1

          for row in rows:
              ans += rows[row] * cols[row]

          return ans


_ Time Complexity:

  O(n^2) - We parse through the entire matrix to rip out the columns.

_ Space Complexity:

  O(n^2) - In the worst case, being all rows and columns are unique, both dictionaries to store the
  counts of the rows and columns will have n keys with each key having a length of n.