[LeetCode] Equal Row and Column Pairs

Problem: 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:

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]

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]

Approach: We can solve it by comparing every row to every column but it will be expensive. We can reduce the time complexity by using hash but how? How can we cache a whole row?

What we can do is we can convert every row and column into a string using a separator so if the row is say | 12 | 30 | 48 | then converted string will be "12#30#48#". Now this converted string can be used as key of the hash, the value of the hash will be the frequency of such row.

With the above approach what we can do is we can hash every row first into the HashTable using the converted string as key. Once we are done with it, we can iterate over every column, convert into the string using same method and if the hash table contains this string then we can add it's value to the result.

That's all!

Implementation in C#:

    public int EqualPairs(int[][] grid)

    {

        int rows = grid?.Length ?? 0;

        if (rows == 0)

        {

            return 0;

        }

        if (rows == 1)

        {

            return 1;

        }

        int cols = grid[0].Length;

        Dictionary<string, int> rowStrs = new Dictionary<string, int>();

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

        {

            StringBuilder rowStr = new StringBuilder();

            for (int j = 0; j < cols; ++j)

            {

                rowStr.Append(grid[i][j].ToString());

                rowStr.Append("#");

            }

            string str = rowStr.ToString();

            if (!rowStrs.ContainsKey(str))

            {

                rowStrs[str] = 0;

            }

            ++rowStrs[str];

        }

        int result = 0;

        for (int j = 0; j < cols; ++j)

        {

            StringBuilder colStr = new StringBuilder();

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

            {

                colStr.Append(grid[i][j].ToString());

                colStr.Append("#");

            }

            string str = colStr.ToString();

            if (rowStrs.ContainsKey(str))

            {

                result += rowStrs[str];

            }

        }

        return result;

    }

Complexity: O(n^2 * log(n))