Python program to find Successive row difference in Matrix

Given a Matrix, the task is to write a Python program to perform differences from the previous row on the basis of the elements present.

Input : test_list = [[5, 6, 3, 1], [7, 5, 3, 1], [3, 2], [7, 3, 3, 2], [2, 3], [9, 8, 1]]

Output : [[], [7], [2], [7], [], [8, 9, 1]]

Explanation : Comparing 1st and 2nd row, only 7 exists in 2nd row and not in 1st hence [7] is output.

Input : test_list = [[5, 6], [7, 5, 3, 1], [3, 4], [7], [2, 9], [9, 8, 1]]

Output : [[], [1, 3, 7], [4], [7], [9, 2], [8, 1]]

Explanation : Comparing 2nd and 3rd list, only 4 is present in 3rd list and not in 2nd, hence output.

Example : Using set.difference() + loop

In this, the previous set is maintained, which keeps the track of the previous set to get the difference. This removes all elements from the current list which are already present in the previous list.

The original list is : [[5, 6, 3, 1], [7, 5, 3, 1], [3, 2], [7, 3, 3, 2], [2, 3], [9, 8, 1]]
Successive Row difference : [[], [7], [2], [7], [], [8, 9, 1]]

Time Complexity: O(n)
Auxiliary Space: O(n)

Method #2: Using Counter() function

The original list is : [[5, 6, 3, 1], [7, 5, 3, 1], [3, 2], [7, 3, 3, 2], [2, 3], [9, 8, 1]]
Successive Row difference : 
[] [7] [2] [7] [] [9, 8, 1] 

Time Complexity: O(n*n)

Space Complexity: O(n)

Method#3: Using Recursive method.

Algorithm:

1. Define a function named successive_row_difference that takes a list as an argument.
2. Check if the input is a non-empty list.
3. Take the first sublist in the list and calculate its difference set with the prev argument (initialized as None for the first call).
4. Recursively call the successive_row_difference function for the remaining sublists in the list, passing the current sublist as the prev argument for the next call.
5. Combine the difference set of the current sublist with the result of the recursive call and return the combined list.
6. If the input list is empty or not a list, return an empty list.
7. Call the successive_row_difference function with the input list and store the result in a variable.
8. Print the result.

The original list is : [[5, 6, 3, 1], [7, 5, 3, 1], [3, 2], [7, 3, 3, 2], [2, 3], [9, 8, 1]]
Successive Row difference : [[7], [2], [7], [], [8, 9, 1]]

Time complexity:

The time complexity of this algorithm is O(n^2), where n is the number of sublists in the input list. This is because the algorithm iterates through each sublist in the list and performs a set operation, which has a time complexity of O(n). Since the algorithm performs this operation for each sublist, the time complexity becomes O(n^2).

Auxiliary Space:

The space complexity of this algorithm is O(n^2), where n is the number of sublists in the input list. This is because the algorithm creates a list to store the difference set between each successive pair of sublists in the input list. Since the list contains n-1 elements and each element may have at most n-1 elements, the space complexity becomes O(n^2).

Method#4: Using lambda function.

In this method, we initialize a matrix of integers called test_list and find the successive row differences in it using the set.difference() method and a lambda function, and then prints both the original matrix and the resulting list of differences.

The original list is : [[5, 6, 3, 1], [7, 5, 3, 1], [3, 2], [7, 3, 3, 2], [2, 3], [9, 8, 1]]
Successive Row difference : [[], [7], [2], [7], [], [8, 9, 1]]

Time Complexity: O(n), where n is the length of the input list test_list.

Auxiliary Space: O(n), as the output list res grows in size linearly with the input list. 

Method#5: Using reduce method:

Algorithm :

1. Import the reduce function from functools.
2. Define the input list test_list.
3. Define an empty list res to store the successive row differences.
4. Set prev to the first row of test_list as a set.
5. Define a lambda function get_difference that takes two arguments, prev and ele. This function finds the difference between ele and prev using the set difference method, appends the result to res, and returns the set ele.
6. Call the reduce function with get_difference as the first argument, test_list as the second argument, and prev as the third argument. This applies the get_difference function to each element of test_list in succession,
7. updating the value of prev for each iteration.
8. Print the original list and the list of successive row differences.

The original list is : [[5, 6, 3, 1], [7, 5, 3, 1], [3, 2], [7, 3, 3, 2], [2, 3], [9, 8, 1]]
Successive Row difference : [[], [7], [2], [7], [], [8, 9, 1]]

The time complexity : O(n), where n is the total number of elements in the input list.

The auxiliary space : O(n), as the list res has a size of n.