Given a list, perform removal of those elements whose difference is less than K from its previous element.
Input : test_list = [3, 19, 5, 8, 10, 13], K = 4
Output : [3, 8, 13, 19]
Explanation : 5 – 3 = 2, 2<4, hence 5 is removed, similarly, 10 – 8 is 2, less than K.Input : test_list = [15, 7, 20], K = 4
Output : [7, 15, 20]
Explanation : No deletion required.
Approach: Using loop and sorted()
In this, first, the list has to be sorted and then removal of elements that do not have appropriate distance between its preceding and succeeding element is performed.
Python3
# initializing listtest_list = [3, 19, 4, 8, 10, 13]# printing original listprint("The original list is : " + str(test_list))# initializing K K = 4# sorting list test_list = sorted(test_list)idx = 0while idx < len(test_list) - 1: # checking for difference if test_list[idx] + K > test_list[idx + 1]: # deleting if K closer del test_list[idx + 1] else: idx += 1# printing result print("Required List : " + str(test_list)) |
Output:
The original list is : [3, 19, 4, 8, 10, 13]
Required List : [3, 8, 13, 19]
Time complexity: O(n log n + n) where n is the number of elements in the list. The sorting takes O(n log n) time, and the while loop takes O(n) time in the worst case.
Auxiliary space: O(n), for storing the sorted list.
Method 2: Using set and list comprehension
- Initialize the list
- Initialize the value of K
- Convert the list to a set to remove duplicates and improve search time
- Create a new list by iterating over the set and checking if K plus the current element is in the set
- Sort the new list in ascending orderPrint the new list
Python3
# initializing listtest_list = [3, 19, 4, 8, 10, 13]# printing original listprint("The original list is : " + str(test_list))# initializing K K = 4# sorting list test_list = sorted(test_list)idx = 0while idx < len(test_list) - 1: # checking for difference if test_list[idx] + K > test_list[idx + 1]: # deleting if K closer del test_list[idx + 1] else: idx += 1# printing result print("Required List : " + str(test_list)) |
The original list is : [3, 19, 4, 8, 10, 13] Required List : [3, 8, 13, 19]
Time complexity: O(n log n) for the sort function and O(n) for iterating over the set and list comprehension, so the total time complexity is O(n log n).
Auxiliary space: O(n) for the set and new list, so the auxiliary space complexity is O(n).
