Last Updated: 1 Mar, 2021

Unique Matrix

Moderate

Asked in companies

Solve now

Problem statement

You are given a binary matrix 'MATRIX' of 'N' rows and 'M' columns.

Your task is to return all the unique rows in the order they appear in the matrix.

For example:

Matrix = [ [1,0,1], [0,0,1 ], [1,0,1 ]] 
Result = [ [1,0,1], [0,0,1] ]. 
The row [1,0,1] is before [0,0,1] as it appears before in matrix.

Note: In the binary matrix, all the entries are either 0 or 1.

Input Format:

The first line of input contains an integer 'T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains two single space-separated integers ‘N’, ‘M’, denoting the number of rows and number of columns in the matrix, respectively. 

The next ‘N’ lines of each test case contain ‘M’ space-separated integers denoting the elements of the binary matrix.

Output Format:

For each test case, print all the unique rows in the order they appear in the matrix.

The output for each test case will be printed in a separate line.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10 
1 <= N <= 3000
1 <= M <= 40 

where ‘N’ and ‘M’ are the number of rows and columns of the matrix, respectively.

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

We store all the result array ANS. We create an unordered set UNIQUE to store a decimal representation of all rows. Iterate over all the rows in the matrix. If the row is not in the set add it to the set and append it to the ANS.

The algorithm will be-

For each row from 0 to N - 1:
1. Convert the current row into its decimal representation.
2. If the current decimal number is not in UNIQUE.
  1. Add it to the UNIQUE.
  2. Append the current row to the ANS.
We finally return ANS.

Solve now

02 Approach

We will iterate over all the rows in the matrix and store them in the trie. When a new row that is not present in trie appears append it to the ANS. To store a row in trie go through the row if the current element in a row is 0 go to the left child and if it is 1 go to the right child.

To know more about trie data structure: link

The algorithm will be-

We create an array ANS to store the final result.
Create a trie with the head pointer.
We now, iterate over all the rows in the matrix.
1. Store the row in the trie.
2. If the current row is not in trie-
  1. Append the current row to the ANS
We finally return the ANS.

Solve now