Python | Group consecutive list elements with tolerance

Sometimes, we might need to group list according to the consecutive elements in the list. But a useful variation of this can also be a case in which we need to consider a tolerance level, i.e allowing a skip value between numbers and not being exactly consecutive but a “gap” is allowed between numbers. Let’s discuss an approach in which this task can be performed. 

Method 1: Using generator 

The brute method to perform this task. Using a loop and generator, one can perform this task. The slicing is taken care of by the yield operator and hence this problem is solved by a small check of tolerance as well.

Time Complexity: O(n)

Space Complexity: O(n)

The original list is : [1, 2, 4, 5, 9, 11, 13, 24, 25, 26, 28]
The splitted list is : [[1, 2, 4, 5], [9, 11, 13], [24, 25, 26, 28]]

Method 2: Using a loop

1. Initialize an empty list groups to store the groups of consecutive elements.
2. Initialize a variable last to store the last element of the previous group. Set last to None initially.
3. Initialize an empty list group to store the current group of consecutive elements.
4. Loop through each element ele in the given list test_list.
5. If last is None, set it to ele and append ele to group. This is the first element of the first group.
6. Else if the difference between ele and last is less than or equal to the tolerance, append ele to group.
7. This element is part of the current group.
8. Else, append the current group to groups and start a new group with ele. This element is the first element of a new group.
9. Set last to ele for the next iteration.
10. Append the last group to groups after the loop ends.
11. Return the list of groups.

[[1, 2, 4, 5], [9, 11, 13], [24, 25, 26, 28]]

Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.