Python | Unique values in Matrix

Sometimes we need to find the unique values in a list, which is comparatively easy and has been discussed earlier. But we can also get a matrix as input i.e a list of lists, and finding unique in them are discussed in this article. Let’s see certain ways in which this can be achieved. 

Method #1: Using set() + list comprehension The set function can be used to convert the individual list to a non-repeating element list and the list comprehension is used to iterate to each of the lists. 

The original matrix is : [[1, 3, 1], [4, 5, 3], [1, 2, 4]]
Unique values in matrix are : [1, 2, 3, 4, 5]

Time complexity: O(n^2), where n is the number of elements in the matrix.
Auxiliary space: O(n), where n is the number of unique elements in the matrix. 

Method #2: Using chain() + set() The chain function performs the similar task that a list comprehension performs but in a faster way as it uses iterators for its internal processing and hence faster. 
 

The original matrix is : [[1, 3, 1], [4, 5, 3], [1, 2, 4]]
Unique values in matrix are : [1, 2, 3, 4, 5]

Time Complexity: O(n), where n is the total number of elements in the matrix.
Auxiliary Space: O(n), for storing the unique elements in the set.

Method #3 : Using for loop and extend(),sort() methods

The original matrix is : [[1, 3, 1], [4, 5, 3], [1, 2, 4]]
Unique values in matrix are : [1, 2, 3, 4, 5]

Time complexity: O(n*logn), where n is the number of elements in the matrix.
Auxiliary space: O(n), where n is the number of unique elements in the matrix. 

Method #4 : Using Counter() function

The original matrix is : [[1, 3, 1], [4, 5, 3], [1, 2, 4]]
Unique values in matrix are : [1, 2, 3, 4, 5]

Time Complexity:O(N*N)
Auxiliary Space: O(N*N)

Method #5: Using operator.countOf() method

The original matrix is : [[1, 3, 1], [4, 5, 3], [1, 2, 4]]
Unique values in matrix are : [1, 2, 3, 4, 5]

Time Complexity: O(N*N)
Auxiliary Space: O(N*N)

Method #6:Using groupby()

The original matrix is : [[1, 3, 1], [4, 5, 3], [1, 2, 4]]
Unique values in matrix are : [1, 2, 3, 4, 5]

Time Complexity: O(N*N)
Auxiliary Space: O(N*N)

Method #7: Using numpy.unique() function

Step-by-step approach:

• Import numpy library.
• Initialize the matrix using numpy.array() function.
• Apply numpy.unique() function on the matrix to get the unique values.
• Convert the returned numpy array to a list using the tolist() method.
• Print the list of unique values.

Below is the implementation of the above approach:

Output: 

The original matrix is : [[1 3 1]
[4 5 3]
[1 2 4]]
Unique values in matrix are : [1, 2, 3, 4, 5]

Time complexity: O(nlogn), where n is the number of elements in the matrix.
Auxiliary space: O(n)

Method #8:Using heapq.merge():

Algorithm
 

1. Import the heapq module.
2. Create a NumPy array test_matrix with shape (3, 3) and values [[1, 3, 1], [4, 5, 3], [1, 2, 4]].
3. Print the original matrix.
4. Use heapq.merge() to merge the rows of test_matrix into a single iterator of sorted elements.
5. Convert the iterator to a set to eliminate duplicates.
6. Print the unique elements of the matrix.

Output:
The original matrix is : [[1 3 1]
[4 5 3]
[1 2 4]]
Unique values in matrix are : [1, 2, 3, 4, 5]

Time Complexity

The time complexity of the code is determined by the most time-consuming operation, which is heapq.merge(). The time complexity of heapq.merge() is O(k * log(n)), where k is the total number of elements in the matrix and n is the number of rows in the matrix. Therefore, the overall time complexity of the code is O(k * log(n)).

Auxiliary Space

The space complexity of the code is determined by the memory used by the data structures created during the execution of the code. The code creates a NumPy array to store the matrix, which requires O(n^2) space, where n is the number of rows or columns in the array. The heapq.merge() function also creates a heap to store the merged elements, which requires O(k) space, where k is the total number of elements in the matrix. Finally, the code creates a set to store the unique elements, which requires O(k) space. Therefore, the overall space complexity of the code is O(n^2 + k).

 Method #9:Using reduce():

Algorithm:

1. Initialize the test_matrix variable with a 2D list.
2. Print the original matrix using the print() function.
3. Import the chain and set functions from the itertools module.
4. Use chain() to flatten the 2D matrix into a single list.
5. Use set() to get the unique elements from the flattened list.
6. Convert the resulting setback to a list using the list() function.
7. Print the list of unique values using the print() function.

Below is the implementation of the above approach:

The original matrix is : [[1, 3, 1], [4, 5, 3], [1, 2, 4]]
Unique values in matrix are: [1, 2, 3, 4, 5]

Time Complexity:

• The chain() function is used to flatten the 2D matrix, which takes O(N) time, where N is the total number of elements in the matrix.
• The set() function takes O(N) time to create a set of unique elements.
• Converting the set back to a list using the list() function takes O(N) time.

Therefore, the overall time complexity of the code is O(N).

Space Complexity:

• The test_matrix variable takes O(N) space to store the 2D matrix.
• The res variable takes O(M) space to store the unique elements, where M is the number of unique elements in the matrix.
• The chain() function and the set() function also take O(N) space.

Therefore, the overall space complexity of the code is O(N).