Efficient algorithm to check duplicate rows in a matrix

Question

Given a matrix M of integers. Check if two rows are identical in the matrix. Give an optimum approach.

Example:
[{1, 2, 3},
 {3, 4, 5},
 {1, 2, 3}]

In the above matrix, rows 1 and 3 are identical.

Possible Solution:

Given a matrix, we can convert each row in a string (example using to_string()
method of C++ and concatenating each element in a row to a string). We do this
for every row of the matrix, and insert it in a table that is something like
(map<string, int> in C++). And hence, duplicate row can be checked in O(mn) time
for an mxn matrix.

Can I do better than this ? Or, above method has any flaw ?

Answer 1

Your method works but you are wrong with the complexity of it.

Firstly, testing if an element is in a std::map has complexity O(log(n) * f), where n is the number of elements in the map and f is an upper bound for the time required to comparing any two elements inserted/searched in the map.

In your case, every string has a length m, so comparing any two elements in the map costs O(m).

So the total complexity of your method is:

O(n * log(n) * m) for inserting n strings in the map.

However, you can speed it up to O(n * m) in expectation, which is asymptotically optimal (because you have to read all the data), using a hash table rather than a map. The reason for this is that a hash table has O(1) average complexity for an insert operation and the hash function for every input string is computed only once.

In C++ you can use the unordered_set for that.