Display Unique Rows in a Binary Matrix in Java
To solve this problem, we must first locate and display the distinct rows of a supplied binary matrix afterward. We will go through how to show distinct rows inside a binary matrix in Java. We will go through how to show distinct rows inside a binary matrix in Java.
Example:
1 0 1 0 1
1 0 0 0 1
1 0 1 0 1
1 1 1 0 0
1 1 0 0 1
Output
1 0 1 0 1
1 0 0 0 1
1 1 1 0 0
1 1 0 0 1
Explanation :
In the above example, the input contains the 5 rows; only some are distinct. In the 5*5 matrix, row 1 and throw 3 are the same. We can eliminate row 3.
Naïve Approach
The naive strategy is straightforward. Print the first rows first, and then verify to see if the back row matches the published row (first row). Print this second row if it doesn't match; trash it. Check this third row to see if it corresponds to the first and third displayed rows. Print this second row if it matches; if not, go to the next row. Apply the same methodology to the remaining rows.
Implementation Steps
The steps below mentioned are used in the process of implementation:
Step 1: Iterate over the matrix row-by-row.
Step 2: Determine if the new row matches the preceding.
Step 3: Else, don't publish the column headings if they match the previous rows.
Step 4: In the absence of it, highlight the current row.
Java Program for printing the distinct matrix rows
UniqueMatrix.java
// this program is for finding the unique rows in the Binary Matrix
//importing the required packages
import java.io.*;
import java.util.*;
public class UniqueMatrix
{
// method for defining the unique rows in the given matrix
public void printdistinctRows(int matrixs[][], int rows, int cl)
{
// iterating over the matrix
for(int j = 0; j < rows; j++)
{
// There are only two possible values for is unique: 0 and 1.
//If the row is distinct,
//it has a value of 1, else it has a value of 0.
int ishaveUnqiue = 0;
// jth and ith columns must match to
//determine whether p previously showed the identical column.
for(int i = 0; i < j; i++)
{
ishaveUnqiue = 0;
for(int k = 0; k < cl; k++)
{
if (matrixs[j][k] != matrixs[i][k])
{
ishaveUnqiue = 1;
}
}
if (ishaveUnqiue == 0)
break;
}
//If either of the rows is the initial
//row, or perhaps the row is distinct
if (ishaveUnqiue == 1 || j == 0)
{
// the rows were displayed
for(int p = 0; p < cl; p++)
{
System.out.print(matrixs[j][p] + " ");
}
System.out.println();
}
}
}
// main section of the program
public static void main(String argvs[])
{
// an object ob was created for the class UniqueMatrix
UniqueMatrix ob = new UniqueMatrix();
// the user input matrix will be given
int matrixs[][] = { { 0, 1, 1, 1, 0 },
{ 1, 1, 0, 1, 1 },
{ 0, 1, 1, 1, 1 },
{ 0, 1, 1, 1, 0 },
{ 0, 0, 1, 1, 1 }
};
// finding the row length in the given matrix
int rows = matrixs.length;
// finding the length of the column in the given matrix
int cl = matrixs[0].length;
System. out.println(" The given matrix is: ");
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cl; j++)
{
System.out.print(matrixs[i][j] + " ");
}
System.out.println();
}
System.out.println();
System.out.println(" The distinct rows in the matrix are : ");
ob.printdistinctRows(matrixs, rows, cl);
System.out.println("\n");
// input binary matrix
int matrixs1[][] = { { 1, 1, 1, 0 },
{ 1, 0, 1, 1 },
{ 1, 0, 1, 0 },
{ 1, 1, 1, 1 }
};
// finding the row length in the given matrix
rows = matrixs1.length;
// finding the length of the column in the given matrix
cl = matrixs1[0].length;
System.out.println(" The given matrix is: ");
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cl; j++)
{
System.out.print(matrixs1[i][j] + " ");
}
System.out.println();
}
System.out.println();
System.out.println(" The distinct rows in the matrix are :");
ob.printdistinctRows(matrixs1, rows, cl);
}
}
Output
The given matrix is:
0 1 1 1 0
1 1 0 1 1
0 1 1 1 1
0 1 1 1 0
0 0 1 1 1
The distinct rows in the matrix are :
0 1 1 1 0
1 1 0 1 1
0 1 1 1 1
0 0 1 1 1
The given matrix is:
1 1 1 0
1 0 1 1
1 0 1 0
1 1 1 1
The distinct rows in the matrix are :
1 1 1 0
1 0 1 1
1 0 1 0
1 1 1 1
Time Complexity: Inside the software mentioned above, we compare each row to the row that came before it to determine whether or not they are unique. Inside the row comparison, we must determine whether or not each component of one row equals that of the opposite row (column size). Since R is the total number of consecutive rows in the matrices and C is the maximum number of rows in the matrix, the running time of the algorithm mentioned above is O(R2 x C). The preceding system's space complexity is equal and constant because we do not access any supplementary arrays O(1).
If we look closely at the program described above, we'll see that many of the problem instances have been solved several times, which is what causes the exponential computation time.
Binary Search Tree as a method
Making each row's decimals equal and inserting them into the tree of binary searches is the initial step in this method. Remember that every node of the binary tree retrieves fields: one that contains the discrete number and another for the previous row.
Adopting Procedures
These procedures are needed to put the binary search tree technique into practice.
- The first step is to ensure that no identical nodes are stored in the Binary Search Tree.
- Create a function in step two to convert a row to a decimal number and to convert a numerical number to a binary array.
- The third step is to iterate through the input sequence and add the row to the search tree.
- The fourth step is to Convert the decimals into the digital array and show the results after doing an in-order traverse of the Binary Tree.
Example: UniqueMatrix1.java
// this program is for finding the unique rows in the Binary Matrix
//importing the required packages
import java.util.*;
public class UniqueMatrix1
{
static class BS
{
int va;
BS lts, rts;
BS(int va)
{
this.va = va;
this.lts = this.rts = null;
}
}
// an array arr is converted to the decimal
static int convertArray(int arr[], int Ct)
{
int st = 0;
for(int j = 0; j < Ct; j++)
{
st += Math.pow(2, j) * arr[j];
}
return st;
}
// in the matrix the column with integer values is printed
static void print(int pt, int Ct)
{
for(int j = 0; j < Ct; j++)
{
System.out.print(pt % 2 + " ");
pt = pt / 2;
}
System.out.println();
}
// method that defines the insert.
static BS Insert(BS rts, int va)
{
if(rts == null)
{
// the condition that the root node is null or not.
return new BS(va);
}
// the variable va is checked with the current variable
if(va == rts.va)
{
return rts;
}
// the information is then appended to the matrix
if(va > rts.va)
{
//If the "value" that must place is greater than
//the "rts" branch value, should place the correct node.
//Handling all appropriate nodes
rts.rts = Insert(rts.rts,va);
}
else
{
//If the "va" that needs to be entered is greater than
//the "rts" node value, the left node data is entered.
//Dealing with the left node.
rts.lts = Insert(rts.lts, va);
}
// the node rts is returned after the insertion process
return rts;
}
// the inorder way of the traversing will give the
// order of the nodes
static void Inorder(BS rts, int Ct)
{
if(rts == null)
{
return;
}
Inorder(rts.lts, Ct);
print( rts.va, Ct);
Inorder(rts.rts, Ct);
}
// the method for printing all the distib=nct rows in the matrix
static void printDistinctRows(int matrix[][], int Row, int Cl)
{
BS b, rts = null;
// Traversing the matrix
for(int j = 0; j < Row; j++)
{
// the values for the row elements are inserted
rts = Insert(rts, convert arrays(matrix[j], Cl));
}
// printing the result
Inorder(rts, Cl);
}
// main section of the program
public static void main(String argvs[])
{
// an object obj is created for the class UniqueMatrix1
UniqueMatrix1 obj = new UniqueMatrix1();
// the user input arry matrix
int maxtrix[][] = { { 1, 1, 0, 0, 0 },
{ 1, 0, 1, 0, 1 },
{ 0, 1, 1, 0, 1 },
{ 0, 0, 1, 1, 0 },
{ 1, 1, 0, 0, 0 }
};
// the length of the rows in the matrix
int rows = maxtrix.length;
// the length of the columns in the matrix
int cl = maxtrix[0].length;
System. out.println(" The given matrix is : ");
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cl; j++)
{
System.out.print(maxtrix[i][j] + " ");
}
System.out.println();
}
System.out.println();
System.out.println(" the distinct rows in the matrix : ");
obj.printDistinctRows(maxtrix, rows, cl);
System.out.println("\n");
// the user input arry matrix
int matrix1[][] = { { 1, 1, 1, 0 },
{ 0, 1, 0, 0 },
{ 0, 1, 0, 0 },
{ 1, 0, 1, 1 }
};
// the length of the rows in the matrix
rows = matrix1.length;
// the length of the columns in the matrix
cl = matrix1[0].length;
System.out.println("The given matrix is :");
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cl; j++)
{
System.out.print(matrix1[i][j] + " ");
}
System.out.println();
}
System.out.println();
System.out.println("the distinct rows in the matrix: ");
obj.printDistinctRows(matrix1, rows, cl);
}
}
Output
The given matrix is :
1 1 0 0 0
1 0 1 0 1
0 1 1 0 1
0 0 1 1 0
1 1 0 0 0
the distinct rows in the matrix :
1 1 0 0 0
0 0 1 1 0
1 0 1 0 1
0 1 1 0 1
The given matrix is :
1 1 1 0
0 1 0 0
0 1 0 0
1 0 1 1
the distinct rows in the matrix:
0 1 0 0
1 1 1 0
1 0 1 1 Complexity Analysis:
The temporal complexity of the program above, which traverses every row and column of both the matrix, is O(R * C). The binary search arrays are stored in the program's supplemental space, which results in a space complexity of O(R), in which R seems to be the source matrix's row length, and C is its column length. Additionally, putting a row inside the binary search tree has an O time complexity (R). The time required for insertion is R * O(log(R)) because we add every row individually. As just a result, the program described above has an O(R * C + R * (log(R))) time complexity.
TRIE Method
Regarding data recovery efficiency, we are aware of the TRIE data model. We can reduce the search's complexity by using the TRIE data structure.
We will use the TRIE database schema to locate the unique rows inside this method. Given that the data matrices is a binary matrices binary, we shall slightly modify our TRIE data structure by ensuring that each node has 2 kids, including one for 1 and another for 0. This is because we already know that such an input matrix is a binary matrix.
Steps for Execution
Construct a TRIE data structure using step 1 to store each row.
Step 2: Iterate over every row and add it to the TRIE data structure built in Step 1. The TRIE data structure is unaffected by traversing the duplication row to add it because the TRIE can never have any data duplication. The distinct rows are, therefore, those that are retained in the TRIE after traversing each row of the input matrix.
Step 3: Browse the rows of the TRIE data structure.
The below program is on the implementation of the TRIE method.
UniqueMatrix2.java
// this program is for finding the unique rows in the Binary Matrix
//importing the required packages
public class UniqueMatrix2 {
// the value of the count is 2
static final int CN = 2;
// trie node
static class TNodes
{
TNodes[] childrens= new TNodes[CN];
// If and just if the node depicts the conclusion of both rows,
//therefore isEndOfRow is false.
boolean isEndOfRows;
TNodes(){
isEndOfRows = false;
for (int j = 0; j < CN; j++)
childrens[j] = null;
}
};
static TNodes rts;
// Implants key to tuple if not already there
//Just label the tree structure if indeed
// the value is indeed the trie datatype prefix.
static boolean insert(int rows[])
{
int lv;
int sizes = rows.length;
int id;
TNodes pCrawl = rts;
boolean isUniques = false;
//There are two directions we may go from each node:
//the first is to follow all 1s, while the other is to follow the zeros.
//Whatever we do is determined by the row's occurrence frequency. array[].
for (lv = 0; lv < sizes; lv++)
{
// idx will always be 0 and 1
id = rows[lv];
//The TRIE is caused by this if statement to
//discard the unnecessary rows.
//The if statement determines whether or not the path has already been traveled.
//If so, no new
//nodes are formed. A node is formed if the path also isn't traversed.
if (pCrawl.childrens[id] == null)
{
pCrawl.childrens[id] = new TNodes();
isUniques = true;
}
pCrawl = pCrawl.childrens[id];
}
// marking the last node as the leaf node
pCrawl.isEndOfRows = true;
return isUniques;
}
// A utility method for displaying the unique rows
void displayRows(int input[][], int rows)
{
int j;
int colSizes = input[0].length;
for(j = 0; j < colSizes; ++j)
{
System.out.print(input[rows][j] + " ");
}
System.out.println();
}
//it is the function that main() function is invoking.
//The procedure calls the displayRow() function after removing the distinct
//columns from the input sequence.
void filterAndPrintUniqueRows(int input[][], int Row, int Ct)
{
rts = new TNodes(); // creating an empty Trie
int j;
// Iterating through all of the rows
for (j = 0; j < Row; ++j)
// inserting a row into the TRIE
if (insert(input[j]))
{
// a unique row is found, display it
displayRows(input, j);
}
}
// main method
public static void main(String argvs[])
{
//creating an object of the class UniqueRowsMatrix2
UniqueMatrix2 ob = new UniqueMatrix2();
// input binary matrix
int maxtrix[][] = { { 1, 1, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 1, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 0 },
{ 1, 0, 1, 1, 0 }
};
// finding the length of the matrix rows
int rows = maxtrix.length;
// finding the number of rows
int cl = maxtrix[0].length;
System.out.println(" The given matrix is: ");
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cl; j++)
{
System.out.print(maxtrix[i][j] + " ");
}
System.out.println();
}
System.out.println();
System.out.println(" the distinct rows are: ");
ob.filterAndPrintUniqueRows(maxtrix, rows, cl);
System.out.println("\n");
// input binary matrix
int matrix1[][] = { { 0, 1, 1, 0 },
{ 1, 0, 1, 0 },
{ 0, 1, 1, 0 },
{ 1, 0, 0, 1 }
};
// the number of rows in the matrix
rows = matrix1.length;
// the number of columns in the matrix
cl = matrix1[0].length;
System.out.println("The given matrix is:");
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cl; j++)
{
System.out.print(matrix1[i][j] + " ");
}
System.out.println();
}
System.out.println();
System.out.println("the distinct rows are:");
ob.filterAndPrintUniqueRows(matrix1, rows, cl);
}
} Output
The given matrix is:
1 1 1 0 0
1 1 0 0 1
1 1 1 0 1
0 1 0 1 0
1 0 1 1 0
the distinct rows are:
1 1 1 0 0
1 1 0 0 1
1 1 1 0 1
0 1 0 1 0
1 0 1 1 0
The given matrix is:
0 1 1 0
1 0 1 0
0 1 1 0
1 0 0 1
the distinct rows are:
0 1 1 0
1 0 1 0
1 0 0 1
Complexity Analysis: The program's running time above is O(R * C) since it traverses every row and column of the matrix. The TRIE data structure is stored in additional space within the program, resulting in a space complexity of O(R * C), whereby R is the source matrix's rows size & C is its column length.
Using The HashSet
We will utilize the HashSet data structure to identify the distinct rows in this method. We know that the HashSet data structure implements the Set interface. As a result, the HashSet cannot include any data duplication. The method entails converting each hashing set row to something like a string and inserting it into the hashing set.
Execution Procedures
- To store the row, start by creating a HashSet data structure.
- Iterate thru every row and add it to the hash data structure you constructed in Step 1. Since identical entries cannot exist in a hashing set, traversing an identical row to add it to the hashing set does not affect the database structure. As a result, the distinct rows are present in the HashSet before traversing every row of the input sequence. Observe that must convert the rows into the String before being inserted into the HashSet.
- Navigate through the HashSet data model and show the columns.
UniqueMatrix3.java
// this program is for finding the unique rows in the Binary Matrix
//importing the required packages
import java.util.HashSet;
public class UniqueMatrix3 {
public void filterAndPrintUniqueRows(int input[][], int Row, int Cl)
{
//implementing the HashSet class
HashSet<String> hss = new HashSet<String>();
for(int j = 0; j < Row; j++)
{
// for storing the strings produced from either the input matrix's row
String strs = "";
// in the iteration, the string is then converted to an integer
for(int i = 0; i < Cl; i++)
{
strs = strs + String.valueOf(input[j][i]);
}
if(!hss.contains(strs))
{
hss.add(strs);
int sizes = strs.length();
// the result contains unique rows
for(int i = 0; i < sizes; i++)
{
System.out.print(strs.charAt(i) + " ");
}
System.out.println();
}
}
}
// main section of the program
public static void main(String argvs[])
{
// an object ob is creadted for the classUniqueMatrix3
UniqueMatrix3 ob = new UniqueMatrix3();
// user array as the input
int maxtrix[][] = { { 1, 1, 1, 0, 1 },
{ 0, 0, 0, 1, 0 },
{ 0, 0, 1, 1, 0 },
{ 1, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 0 }
};
// the number of rows in the given matrix
int rows = maxtrix.length;
// the number of columns in the given matrix
int cl = maxtrix[0].length;
System.out.println(" In the matrix given:");
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cl; j++)
{
System.out.print(maxtrix[i][j] + " ");
}
System.out.println();
}
System.out.println();
System.out.println("The distinct rows in the matrix : ");
ob.filterAndPrintUniqueRows(maxtrix, rows, cl);
System.out.println("\n");
// user array 2-d as the binary matrix
int matrix1[][] = { { 1, 0, 0, 1 },
{ 0, 1, 0, 0 },
{ 0, 1, 1, 1 },
{ 0, 1, 0, 0 }
};
// the number of rows in the given matrix
rows = matrix1.length;
// the number of columns in the given matrix
cl = matrix1[0].length;
System.out.println(" In the matrix given:");
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cl; j++)
{
System.out.print(matrix1[i][j] + " ");
}
System.out.println();
}
System.out.println();
System.out.println("The distinct rows in the matrix : ");
ob.filterAndPrintUniqueRows(matrix1, rows, cl);
}
} Output
In the matrix given:
1 1 1 0 1
0 0 0 1 0
0 0 1 1 0
1 1 1 0 0
0 0 1 0 0
The distinct rows in the matrix :
1 1 1 0 1
0 0 0 1 0
0 0 1 1 0
1 1 1 0 0
0 0 1 0 0
In the matrix given:
1 0 0 1
0 1 0 0
0 1 1 1
0 1 0 0
The distinct rows in the matrix :
1 0 0 1
0 1 0 0
0 1 1 1 Complexity Analysis: The temporal complexity of a previous program, which traverses every row and column of the matrices, is O(R * C). This program uses the supplementary space for storing the Hashing data structure, resulting in a space complexity of O(R * C), wherein R is the source matrix's rows size, and Cl is its column number.