Unique Matrix

Moderate
0/80
Average time to solve is 15m
9 upvotes
Asked in company
Ola

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
1 1
1
3 2
1 0
1 1
0 0
Sample Output 1:
1
1 0
1 1
0 0
Explanation of Sample Input 1:
For the first case, there is only one row in the matrix [ [1] ].

For the second test case, all the rows are unique, and they are printed in the order they appear in the matrix.
Sample Input 2:
2
2 5
0 0 0 0 0
1 0 0 0 0
5 2
0 1
0 0
0 0
0 0
0 0
Sample Output 2:
0 0 0 0 0
1 0 0 0 0
0 1
0 0
Hint

Can we convert each row to an equivalent integer representation?

Approaches (2)
Unordered Set

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-

  1. 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.
  2. We finally return ANS.
Time Complexity

O(N * M), where N is the number of rows and M is the number of columns of the binary matrix.

 

Since every element of the matrix will be visited utmost once the time complexity will be O(N * M).

Space Complexity

O(N), Where N is the number of rows of the binary matrix.

 

The space complexity due to the unordered set UNIQUE can be O(N) in the worst case.

Code Solution
(100% EXP penalty)
Unique Matrix
Full screen
Console