Find Duplicate rows in a binary matrix

Find duplicate rows present in a given binary matrix by traversing the matrix only once.

 

Approach 1 (Using Trie) –

 

The idea is to insert each row of given binary matrix into a binary trie. The alphabet size of a binary trie is only limited to Boolean numbers (0 and 1). If we have seen a row before (i.e. it is already present in the trie), we report it as duplicate.

 
C++ implementation –
 

Download   Run Code

Output:

Duplicate row found : Row #3
Duplicate row found : Row #5

 

Approach 2 (Converting to Decimal) –

 

The idea is to convert each row into its decimal equivalent and check if decimal value is seen before or not. If it is seen before, we report the row as duplicate. This method will only work for N < 32 (or N < 64 if long is used) where N is number of columns in the matrix.   C++ implementation –
 

Download   Run Code

Output:

Duplicate row found : Row #3
Duplicate row found : Row #5

 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂