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):
        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.

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.

New Comment





Categories
Relative Post