Posted on by Kalkicode
Code Tree

# Find duplicate rows in a binary matrix

The problem at hand is to find duplicate rows in a binary matrix. A binary matrix is a matrix consisting of only 0s and 1s. Duplicate rows are those rows that have the exact same elements in the same order. The goal is to efficiently identify and report these duplicate rows.

## Problem Description

Imagine you have a matrix where each row represents a sequence of binary values, like this:

``````1 0 1 1 0 1 1
0 0 0 1 0 1 1
1 0 1 1 0 1 1
0 0 0 0 0 0 0
1 0 1 1 0 1 1
0 0 0 0 0 0 0
1 0 0 1 0 1 1
0 0 0 1 0 1 1``````

In this matrix, rows 2, 4, and 7 are exact duplicates of rows 1, 3, and 6, respectively. Similarly, rows 5 and 8 are duplicate of each other.

## Idea to Solve

One way to solve this problem is by using a Trie Tree data structure. A Trie (pronounced "try") is a tree-like data structure that is used to store a dynamic set of strings, where the keys are usually strings. It is often used for efficiently searching for a word in a dictionary.

## Algorithm

1. Create a class called `Node` that represents a node in the Trie Tree. Each node has two children pointers (for 0 and 1) and a boolean `end` flag indicating if it represents the end of a sequence.

2. Create a class called `TrieTree` that represents the Trie Tree. It contains a root node pointer and has methods to insert rows and display the matrix.

3. In the `TrieTree` class, implement an `insert` method that takes a binary row and its length as inputs. Traverse the row from left to right, and for each value (0 or 1), traverse the Trie Tree. If the node corresponding to the value does not exist, create a new node. If the traversal is successful and the end of the row is reached, mark the last node as the end of the sequence.

4. In the `main` function, create an instance of `TrieTree`. Define the binary matrix.

5. For each row in the matrix, use the `insert` method of the `TrieTree` instance. If the insertion is successful (i.e., no previous sequence was already represented by the same path in the Trie Tree), then print that the row is a duplicate.

## Pseudocode

``````class Node:
end = False
children = [None, None]

class TrieTree:
root = Node()

function insert(row[], cols):
status = true
for level in range(cols):
index = row[level]
status = false
return status

matrix = [...]  # The binary matrix
obj = TrieTree()
for i in range(rows):
status = obj.insert(matrix[i], cols)
if status is true:
print("Row", i, "are Duplicate")``````

## Code Solution

``````/*
C++ program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
#include<iostream>
#define R 8
#define C 7
using namespace std;
class Node
{
public:
//Indicates end of string
bool end;
Node **children;
Node()
{
this->end = false;
this->children = new Node*;
}
};
class TrieTree
{
public: Node *root;
TrieTree()
{
this->root = new Node();
}
bool insert(int row[], int cols)
{
//This variable are used to task find the index location of character
int index = 0;
//get the root node
bool status = true;
for (int level = 0; level < cols; level++)
{
//Get the index
index = row[level];
{
//When need to add new Node
//when modified trie tree
status = false;
}
}
{
//indicates end of string
}
return status;
}
void display(int matrix[R][C], int rows, int cols)
{
for (int i = 0; i < rows; ++i)
{
cout << " Row [" << i << "] : ";
for (int j = 0; j < cols; ++j)
{
cout << " " << matrix[i][j];
}
cout << "\n";
}
cout << "\n";
}
};
int main()
{
//Make object
TrieTree obj =  TrieTree();
int matrix[R][C] = {
{
1,
0,
1,
1,
0,
1,
1
},
{
0,
0,
0,
1,
0,
1,
1
},
{
1,
0,
1,
1,
0,
1,
1
},
{
0,
0,
0,
0,
0,
0,
0
},
{
1,
0,
1,
1,
0,
1,
1
},
{
0,
0,
0,
0,
0,
0,
0
},
{
1,
0,
0,
1,
0,
1,
1
},
{
0,
0,
0,
1,
0,
1,
1
},

};
bool status = false;
obj.display(matrix, R, C);
for (int i = 0; i < R; i++)
{
//pass row matrix[i]
status = obj.insert(matrix[i], C);
if (status == true)
{
cout << " Row "<<i<<" are Duplicate\n";
}
}
return 0;
}``````

#### Output

`````` Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 1 0 1 1
Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 0 0 0 0
Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 0 0 0 0
Row  :  1 0 0 1 0 1 1
Row  :  0 0 0 1 0 1 1

Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate``````
``````/*
C# program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
using System;
public class Node
{
//Indicates end of string
public Boolean end;
public Node[] children;
public
Node()
{
end = false;
children = new Node;
}
}
public class TrieTree
{
public Node root;
public TrieTree()
{
root = new Node();
}
public Boolean insert(int [,]matrix,int row, int cols)
{
//This variable are used to task find the index location of character
int index = 0;
//get the root node
Boolean status = true;
for (int level = 0; level < cols; level++)
{
//Get the index
index = matrix[row,level];
{
//When need to add new Node
//when modified trie tree
status = false;
}
}
{
//indicates end of string
}
return status;
}
public void display(int[,] matrix, int rows, int cols)
{
for (int i = 0; i < rows; i++)
{
Console.Write(" Row [" + i + "] : ");
for (int j = 0; j < cols; j++)
{
Console.Write(" " + matrix[i,j]);
}
Console.Write("\n");
}
Console.Write("\n");
}
public static void Main(String[] args)
{
//Make object
TrieTree obj = new TrieTree();
int [,] matrix =     {
{1,0,1,1,0,1,1},
{0,0,0,1,0,1,1},
{1,0,1,1,0,1,1},
{0,0,0,0,0,0,0},
{1,0,1,1,0,1,1},
{0,0,0,0,0,0,0},
{1,0,0,1,0,1,1},
{0,0,0,1,0,1,1}
};

Boolean status = false;
//Get the size of matrix
int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);
obj.display(matrix, rows, cols);
for (int i = 0; i < rows; i++)
{
//pass row matrix[i]
status = obj.insert(matrix,i, cols);
if (status == true)
{
Console.Write(" Row " + i + " are Duplicate\n");
}
}
}
}``````

#### Output

`````` Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 1 0 1 1
Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 0 0 0 0
Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 0 0 0 0
Row  :  1 0 0 1 0 1 1
Row  :  0 0 0 1 0 1 1

Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate``````
``````/*
Java program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
class Node
{
//Indicates end of string
public boolean end;
public Node[] children;
public Node()
{
end = false;
children = new Node;
}
}
public class TrieTree
{
public Node root;
public TrieTree()
{
root = new Node();
}
public boolean insert(int []row,int cols)
{

//This variable are used to task find the index location of character
int index = 0;
//get the root node
boolean status = true;
for (int level = 0; level < cols; level++)
{
//Get the index
index = row[level];
{
//When need to add new Node
//when modified trie tree
status = false;
}
}
{
//indicates end of string
}
return status;
}
public void display(int[][] matrix,int rows,int cols)
{

for (int i = 0; i < rows; ++i)
{
System.out.print(" Row  [" + i + "] : ");
for (int j = 0; j < cols; ++j)
{
System.out.print("  " + matrix[i][j]);
}
System.out.print("\n");
}
System.out.print("\n");
}
public static void main(String[] args)
{
//Make object
TrieTree obj = new TrieTree();
int matrix[][] =
{
{1,0,1,1,0,1,1},
{0,0,0,1,0,1,1},
{1,0,1,1,0,1,1},
{0,0,0,0,0,0,0},
{1,0,1,1,0,1,1},
{0,0,0,0,0,0,0},
{1,0,0,1,0,1,1},
{0,0,0,1,0,1,1},
};
boolean status = false;
//Get the size of matrix

int rows = matrix.length;
int cols = matrix.length;
obj.display(matrix,rows,cols);

for (int i = 0; i < rows; i++)
{
//pass row matrix[i]
status = obj.insert(matrix[i],cols);
if (status == true)
{
System.out.print(" Row "+i+" are Duplicate\n");
}
}
}
}``````

#### Output

`````` Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 1 0 1 1
Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 0 0 0 0
Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 0 0 0 0
Row  :  1 0 0 1 0 1 1
Row  :  0 0 0 1 0 1 1

Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate``````
``````<?php
/*
Php program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
class Node
{
//Indicates end of string
public \$end;
public \$children;

function __construct()
{
\$this->end = false;
\$this->children = array_fill(0, 2, null);
}
}
class TrieTree
{
public \$root;

function __construct()
{
\$this->root = new Node();
}
public 	function insert( & \$row, \$cols)
{
//This variable are used to task find the index location of character
\$index = 0;
//get the root node
\$status = true;
for (\$level = 0; \$level < \$cols; \$level++)
{
//Get the index
\$index = \$row[\$level];
{
//When need to add new Node
//when modified trie tree
\$status = false;
}
}
{
//indicates end of string
}
return \$status;
}
public 	function display( & \$matrix, \$rows, \$cols)
{
for (\$i = 0; \$i < \$rows; ++\$i)
{
echo(" Row [". \$i ."] : ");
for (\$j = 0; \$j < \$cols; ++\$j)
{
echo(" ". \$matrix[\$i][\$j]);
}
echo("\n");
}
echo("\n");
}
}

function main()
{
//Make object
\$obj = new TrieTree();
\$matrix = array(array(1, 0, 1, 1, 0, 1, 1),
array(0, 0, 0, 1, 0, 1, 1),
array(1, 0, 1, 1, 0, 1, 1),
array(0, 0, 0, 0, 0, 0, 0),
array(1, 0, 1, 1, 0, 1, 1),
array(0, 0, 0, 0, 0, 0, 0),
array(1, 0, 0, 1, 0, 1, 1),
array(0, 0, 0, 1, 0, 1, 1));
\$status = false;
//Get the size of matrix
\$rows = count(\$matrix);
\$cols = count(\$matrix);
\$obj->display(\$matrix, \$rows, \$cols);
for (\$i = 0; \$i < \$rows; \$i++)
{
//pass row matrix[i]
\$status = \$obj->insert(\$matrix[\$i], \$cols);
if (\$status == true)
{
echo(" Row ". \$i ." are Duplicate\n");
}
}
}
main();``````

#### Output

`````` Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 1 0 1 1
Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 0 0 0 0
Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 0 0 0 0
Row  :  1 0 0 1 0 1 1
Row  :  0 0 0 1 0 1 1

Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate``````
``````/*
Node Js program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
class Node
{
//Indicates end of string
constructor()
{
this.end = false;
this.children = Array(2).fill(null);
}
}
class TrieTree
{
constructor()
{
this.root = new Node();
}
insert(row, cols)
{
//This variable are used to task find the index location of character
var index = 0;
//get the root node
var status = true;
for (var level = 0; level < cols; level++)
{
//Get the index
index = row[level];
{
//When need to add new Node
//when modified trie tree
status = false;
}
}
{
//indicates end of string
}
return status;
}
display(matrix, rows, cols)
{
for (var i = 0; i < rows; ++i)
{
process.stdout.write(" Row [" + i + "] : ");
for (var j = 0; j < cols; ++j)
{
process.stdout.write(" " + matrix[i][j]);
}
process.stdout.write("\n");
}
process.stdout.write("\n");
}
}

function main(args)
{
//Make object
var obj = new TrieTree();
var matrix = [
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1]
];
var status = false;
//Get the size of matrix
var rows = matrix.length;
var cols = matrix.length;
obj.display(matrix, rows, cols);
for (var i = 0; i < rows; i++)
{
//pass row matrix[i]
status = obj.insert(matrix[i], cols);
if (status == true)
{
process.stdout.write(" Row " + i + " are Duplicate\n");
}
}
}
main();``````

#### Output

`````` Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 1 0 1 1
Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 0 0 0 0
Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 0 0 0 0
Row  :  1 0 0 1 0 1 1
Row  :  0 0 0 1 0 1 1

Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate``````
``````#
#   Python 3 program
#   Find duplicate rows in a binary matrix
#   Using Trie Tree

class Node :
# Indicates end of string

def __init__(self) :
self.end = False
self.children = [None] * 2

class TrieTree :

def __init__(self) :
self.root = Node()

def insert(self, row, cols) :
# This variable are used to task find the index location of character
index = 0
# get the root node
status = True
level = 0
while (level < cols) :
# Get the index
index = row[level]
# When need to add new Node
# when modified trie tree
status = False

level += 1

# indicates end of string

return status

def display(self, matrix, rows, cols) :
i = 0
while (i < rows) :
print(" Row [", i ,"] : ", end = "")
j = 0
while (j < cols) :
print(" ", matrix[i][j], end = "")
j += 1

print("\n", end = "")
i += 1

print("\n", end = "")

def main() :
# Make object
obj = TrieTree()
matrix = [
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1]
]
status = False
# Get the size of matrix
rows = len(matrix)
cols = len(matrix)
obj.display(matrix, rows, cols)
i = 0
while (i < rows) :
# pass row matrix[i]
status = obj.insert(matrix[i], cols)
if (status == True) :
print(" Row ", i ," are Duplicate\n", end = "")

i += 1

if __name__ == "__main__": main()``````

#### Output

`````` Row [ 0 ] :   1  0  1  1  0  1  1
Row [ 1 ] :   0  0  0  1  0  1  1
Row [ 2 ] :   1  0  1  1  0  1  1
Row [ 3 ] :   0  0  0  0  0  0  0
Row [ 4 ] :   1  0  1  1  0  1  1
Row [ 5 ] :   0  0  0  0  0  0  0
Row [ 6 ] :   1  0  0  1  0  1  1
Row [ 7 ] :   0  0  0  1  0  1  1

Row  2  are Duplicate
Row  4  are Duplicate
Row  5  are Duplicate
Row  7  are Duplicate``````
``````#   Ruby program
#   Find duplicate rows in a binary matrix
#   Using Trie Tree

class Node
# Define the accessor and reader of class Node
attr_accessor :last,  :children

# Indicates end of string

def initialize()

@last = false
@children = Array.new(2) {nil}
end
end
class TrieTree
# Define the accessor and reader of class TrieTree
attr_accessor :root

def initialize()

@root = Node.new()
end
def insert(row, cols)

# This variable are used to task find the index location of character
index = 0
# get the root node
status = true
level = 0
while (level < cols)

# Get the index
index = row[level]

# When need to add new Node
# when modified trie tree
status = false
end
level += 1
end

# indicates end of string
end
return status
end
def display(matrix, rows, cols)

i = 0
while (i < rows)

print(" Row [", i ,"]  :")
j = 0
while (j < cols)

print(" ", matrix[i][j])
j += 1
end
print("\n")
i += 1
end
print("\n")
end
end
def main()

# Make object
obj = TrieTree.new()
matrix = [
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1]
]
status = false
# Get the size of matrix
rows = matrix.length
cols = matrix.length
obj.display(matrix, rows, cols)
i = 0
while (i < rows)

# pass row matrix[i]
status = obj.insert(matrix[i], cols)
if (status == true)

print(" Row ", i ," are Duplicate\n")
end
i += 1
end
end
main()``````

#### Output

`````` Row   : 1 0 1 1 0 1 1
Row   : 0 0 0 1 0 1 1
Row   : 1 0 1 1 0 1 1
Row   : 0 0 0 0 0 0 0
Row   : 1 0 1 1 0 1 1
Row   : 0 0 0 0 0 0 0
Row   : 1 0 0 1 0 1 1
Row   : 0 0 0 1 0 1 1

Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate
``````
``````/*
Scala program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
class Node(var last: Boolean,
var children: Array[Node])
{
//Indicates end of string
def this()
{
this(false,Array.fill[Node](2)(null));
}
}
class TrieTree(var root: Node)
{
def this()
{
this(new Node());
}
def insert(row: Array[Int], cols: Int): Boolean = {
//This variable are used to task find the index location of character
var index: Int = 0;
//get the root node
var status: Boolean = true;
var level: Int = 0;
while (level < cols)
{
//Get the index
index = row(level);
{
//When need to add new Node
//when modified trie tree
status = false;
}
level += 1;
}
{
//indicates end of string
}
return status;
}
def display(matrix: Array[Array[Int]], rows: Int, cols: Int): Unit = {
var i: Int = 0;
while (i < rows)
{
print(" Row [" + i + "] : ");
var j: Int = 0;
while (j < cols)
{
print(" " + matrix(i)(j));
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Make object
var obj: TrieTree = new TrieTree();
var matrix: Array[Array[Int]] = Array(
Array(1, 0, 1, 1, 0, 1, 1),
Array(0, 0, 0, 1, 0, 1, 1),
Array(1, 0, 1, 1, 0, 1, 1),
Array(0, 0, 0, 0, 0, 0, 0),
Array(1, 0, 1, 1, 0, 1, 1),
Array(0, 0, 0, 0, 0, 0, 0),
Array(1, 0, 0, 1, 0, 1, 1),
Array(0, 0, 0, 1, 0, 1, 1));
var status: Boolean = false;
//Get the size of matrix
var rows: Int = matrix.length;
var cols: Int = matrix(0).length;
obj.display(matrix, rows, cols);
var i: Int = 0;
while (i < rows)
{
//pass row matrix[i]
status = obj.insert(matrix(i), cols);
if (status == true)
{
print(" Row " + i + " are Duplicate\n");
}
i += 1;
}
}
}``````

#### Output

`````` Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 1 0 1 1
Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 0 0 0 0
Row  :  1 0 1 1 0 1 1
Row  :  0 0 0 0 0 0 0
Row  :  1 0 0 1 0 1 1
Row  :  0 0 0 1 0 1 1

Row 2 are Duplicate
Row 4 are Duplicate
Row 5 are Duplicate
Row 7 are Duplicate``````
``````/*
Swift program
Find duplicate rows in a binary matrix
Using Trie Tree
*/
class Node
{
//Indicates end of string
var last: Bool;
var children: [Node?]=[Node]();
init()
{
self.last = false;
var i = 0;
while (i<2) {
self.children.append(nil);
i+=1;
}
}
}
class TrieTree
{
var root: Node? ;
init()
{
self.root = Node();
}
func insert(_ row: [Int], _ cols: Int) -> Bool
{
//This variable are used to task find the index location of character
var index: Int = 0;
//get the root node
var status: Bool = true;
var level: Int = 0;
while (level < cols)
{
//Get the index
index = row[level];
{
//When need to add new Node
//when modified trie tree
status = false;
}
level += 1;
}
{
//indicates end of string
}
return status;
}
func display(_ matrix: [
[Int]
], _ rows: Int, _ cols: Int)
{
var i: Int = 0;
while (i < rows)
{
print(" Row [", i ,"] : ", terminator: "");
var j: Int = 0;
while (j < cols)
{
print(" ", matrix[i][j], terminator: "");
j += 1;
}
print("\n", terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
func main()
{
//Make object
let obj: TrieTree = TrieTree();
var matrix : [[Int]] = [
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1, 1]
];
var status: Bool = false;
//Get the size of matrix
let rows: Int = matrix.count;
let cols: Int = matrix.count;
obj.display(matrix, rows, cols);
var i: Int = 0;
while (i < rows)
{
//pass row matrix[i]
status = obj.insert(matrix[i], cols);
if (status == true)
{
print(" Row ", i ," are Duplicate\n", terminator: "");
}
i += 1;
}
}
main();``````

#### Output

`````` Row [ 0 ] :   1  0  1  1  0  1  1
Row [ 1 ] :   0  0  0  1  0  1  1
Row [ 2 ] :   1  0  1  1  0  1  1
Row [ 3 ] :   0  0  0  0  0  0  0
Row [ 4 ] :   1  0  1  1  0  1  1
Row [ 5 ] :   0  0  0  0  0  0  0
Row [ 6 ] :   1  0  0  1  0  1  1
Row [ 7 ] :   0  0  0  1  0  1  1

Row  2  are Duplicate
Row  4  are Duplicate
Row  5  are Duplicate
Row  7  are Duplicate``````

## Time Complexity

• Inserting a row into the Trie Tree takes O(cols), where `cols` is the number of columns in the matrix.
• In the worst case, when all rows are distinct, the time complexity is O(rows * cols).
• However, if there are many duplicate rows, the Trie Tree helps in reducing the effective search space.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post