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.
Below is C++ and Java implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <iostream> using namespace std; // M x N matrix #define M 5 #define N 5 // A Trie node struct Trie { bool isLeaf; // set when node is a leaf node Trie* character[2]; }; // Function that returns a new Trie node Trie* getNewTrieNode() { Trie* node = new Trie; node->character[0] = node->character[1] = nullptr; node->isLeaf = false; return node; } // Iterative function to insert array in Trie. bool insert(Trie*& head, bool* arr) { // start from root node Trie* curr = head; for (int i = 0; i < N; i++) { // create a new node if path doesn't exists if (curr->character[arr[i]] == nullptr) { curr->character[arr[i]] = getNewTrieNode(); } // go to next node curr = curr->character[arr[i]]; } // if row is inserted before, return false if (curr->isLeaf) { return false; } // mark leaf node and return true return curr->isLeaf = true; } // main function int main() { Trie* head = getNewTrieNode(); bool mat[M][N] = { {1, 0, 0, 1, 0}, {0, 1, 1, 0, 0}, {1, 0, 0, 1, 0}, {0, 0, 1, 1, 0}, {0, 1, 1, 0, 0} }; // insert all rows of into trie for (int i = 0; i < M; i++) { if (!insert(head, mat[i])) { cout << "Duplicate row found: Row #" << i + 1 << '\n'; } } return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
// A class representing a Trie node class Trie { boolean isLeaf; // set when node is a leaf node Trie[] character = new Trie[2]; // Constructor Trie() { isLeaf = false; } }; class Util { // Iterative function to insert array in Trie. public static boolean insert(Trie head, int[] A) { // start from root node Trie curr = head; for(int i = 0; i < A.length; i++) { // create a new node if path doesn't exists if (curr.character[A[i]] == null) { curr.character[A[i]] = new Trie(); } // go to next node curr = curr.character[A[i]]; } // if row is inserted before, return false if (curr.isLeaf) { return false; } // mark leaf node and return true return (curr.isLeaf = true); } public static void main (String[] args) { Trie head = new Trie(); int mat[][] = { {1, 0, 0, 1, 0}, {0, 1, 1, 0, 0}, {1, 0, 0, 1, 0}, {0, 0, 1, 1, 0}, {0, 1, 1, 0, 0} }; // insert all rows of into trie for (int i = 0; i < mat.length; i++) { if (!insert(head, mat[i])) { System.out.println("Duplicate row found: Row #" + (i + 1)); } } } } |
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++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <iostream> #include <unordered_set> #include <cmath> using namespace std; // M x N matrix #define M 5 #define N 5 // main function int main() { bool mat[M][N] = { {0, 0, 0, 0, 0}, {0, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 1, 1, 0}, {0, 1, 1, 0, 0} }; unordered_set<unsigned> set; // do for each row i for (int i = 0; i < M; i++) { unsigned decimal = 0; // convert binary row i into its decimal equivalent for (int j = 0; j < N; j++) { decimal += mat[i][j] * pow(2, j); } // if decimal value is seen before if (set.find(decimal) != set.end()) { cout << "Duplicate row found : Row #" << i + 1 << endl; } else { set.insert(decimal); } } return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import java.util.HashSet; import java.util.Set; class Util { public static void main(String[] args) { int M[][] = { {0, 0, 0, 0, 0}, {0, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 1, 1, 0}, {0, 1, 1, 0, 0} }; Set<Integer> set = new HashSet<>(); // do for each row i for (int i = 0; i < M.length; i++) { int decimal = 0; // convert binary row i into its decimal equivalent for (int j = 0; j < M[i].length; j++) { decimal += M[i][j] * Math.pow(2, j); } // if decimal value is seen before if (set.contains(decimal)) { System.out.println("Duplicate row found : Row #" + (i + 1)); } else { set.add(decimal); } } } } |
Output:
Duplicate row found : Row #3
Duplicate row found : Row #5
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply