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
-
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 booleanend
flag indicating if it represents the end of a sequence. -
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. -
In the
TrieTree
class, implement aninsert
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. -
In the
main
function, create an instance ofTrieTree
. Define the binary matrix. -
For each row in the matrix, use the
insert
method of theTrieTree
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):
head = root
status = true
for level in range(cols):
index = row[level]
if head.children[index] is None:
head.children[index] = Node()
status = false
head = head.children[index]
head.end = true
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*[2];
}
};
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
Node *head = this->root;
bool status = true;
for (int level = 0; level < cols; level++)
{
//Get the index
index = row[level];
if (head->children[index] == NULL)
{
//When need to add new Node
head->children[index] = new Node();
//when modified trie tree
status = false;
}
head = head->children[index];
}
if (head != NULL)
{
//indicates end of string
head->end = true;
}
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 [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
/*
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[2];
}
}
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
Node head = root;
Boolean status = true;
for (int level = 0; level < cols; level++)
{
//Get the index
index = matrix[row,level];
if (head.children[index] == null)
{
//When need to add new Node
head.children[index] = new Node();
//when modified trie tree
status = false;
}
head = head.children[index];
}
if (head != null)
{
//indicates end of string
head.end = true;
}
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 [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
/*
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[2];
}
}
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
Node head = root;
boolean status = true;
for (int level = 0; level < cols; level++)
{
//Get the index
index = row[level];
if (head.children[index] == null)
{
//When need to add new Node
head.children[index] = new Node();
//when modified trie tree
status = false;
}
head = head.children[index];
}
if (head != null)
{
//indicates end of string
head.end = true;
}
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[0].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 [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
<?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
$head = $this->root;
$status = true;
for ($level = 0; $level < $cols; $level++)
{
//Get the index
$index = $row[$level];
if ($head->children[$index] == null)
{
//When need to add new Node
$head->children[$index] = new Node();
//when modified trie tree
$status = false;
}
$head = $head->children[$index];
}
if ($head != null)
{
//indicates end of string
$head->end = true;
}
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[0]);
$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 [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
/*
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 head = this.root;
var status = true;
for (var level = 0; level < cols; level++)
{
//Get the index
index = row[level];
if (head.children[index] == null)
{
//When need to add new Node
head.children[index] = new Node();
//when modified trie tree
status = false;
}
head = head.children[index];
}
if (head != null)
{
//indicates end of string
head.end = true;
}
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[0].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 [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
#
# 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
head = self.root
status = True
level = 0
while (level < cols) :
# Get the index
index = row[level]
if (head.children[index] == None) :
# When need to add new Node
head.children[index] = Node()
# when modified trie tree
status = False
head = head.children[index]
level += 1
if (head != None) :
# indicates end of string
head.end = True
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[0])
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_reader :last, :children
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_reader :root
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
head = @root
status = true
level = 0
while (level < cols)
# Get the index
index = row[level]
if (head.children[index] == nil)
# When need to add new Node
head.children[index] = Node.new()
# when modified trie tree
status = false
end
head = head.children[index]
level += 1
end
if (head != nil)
# indicates end of string
head.last = true
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[0].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 [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
/*
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 head: Node = root;
var status: Boolean = true;
var level: Int = 0;
while (level < cols)
{
//Get the index
index = row(level);
if (head.children(index) == null)
{
//When need to add new Node
head.children(index) = new Node();
//when modified trie tree
status = false;
}
head = head.children(index);
level += 1;
}
if (head != null)
{
//indicates end of string
head.last = true;
}
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 [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
/*
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 head: Node? = self.root;
var status: Bool = true;
var level: Int = 0;
while (level < cols)
{
//Get the index
index = row[level];
if (head!.children[index] == nil)
{
//When need to add new Node
head!.children[index] = Node();
//when modified trie tree
status = false;
}
head = head!.children[index];
level += 1;
}
if (head != nil)
{
//indicates end of string
head!.last = true;
}
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[0].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.
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.
New Comment