Given a list of integers, write a Python program to find groups of strictly increasing numbers.
Examples:
Input : [1, 2, 3, 5, 6] Output : [[1, 2, 3], [5, 6]] Input : [8, 9, 10, 7, 8, 1, 2, 3] Output : [[8, 9, 10], [7, 8], [1, 2, 3]]
Approach #1 : Pythonic naive This is a naive approach which uses an extra input list space. It makes use of a for loop and in every iteration, it checks if the next element increments from previous by 1. If yes, append it to the current sublist, otherwise, create another sublist.
Python3
# Python3 program to Find groups # of strictly increasing numbers within def groupSequence(lst): res = [[lst[0]]] for i in range(1, len(lst)): if lst[i-1]+1 == lst[i]: res[-1].append(lst[i]) else: res.append([lst[i]]) return res # Driver program l = [8, 9, 10, 7, 8, 1, 2, 3]print(groupSequence(l)) |
[[8, 9, 10], [7, 8], [1, 2, 3]]
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n).
Approach #2 : Alternate naive This is an alternative to the above mentioned naive approach. This method is quite simple and straight. It constructs a start_bound list and an end_bound list, which contains the position of starting and ending sequence of increasing integers. Thus simply return the bounds using for loops.
Python3
# Python3 program to Find groups # of strictly increasing numbers within def groupSequence(l): start_bound = [i for i in range(len(l)-1) if (l == 0 or l[i] != l[i-1]+1) and l[i + 1] == l[i]+1] end_bound = [i for i in range(1, len(l)) if l[i] == l[i-1]+1 and (i == len(l)-1 or l[i + 1] != l[i]+1)] return [l[start_bound[i]:end_bound[i]+1] for i in range(len(start_bound))] # Driver program l = [8, 9, 10, 7, 8, 1, 2, 3]print(list(groupSequence(l))) |
[[8, 9, 10], [7, 8], [1, 2, 3]]
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n), as two additional lists are created with a maximum size of n.
Approach #3 : Using iterable and yield This approach uses another list ‘res’ and an iterable ‘it’. A variable ‘prev’ is used for keeping the record of previous integer and start is used for getting the starting position of the increasing sequence. Using a loop, in every iteration, we check if start element is a successor of prev or not. If yes, we append it to res, otherwise, we simply yield the res + [prev] as list element.
Python3
# Python3 program to Find groups # of strictly increasing numbers within def groupSequence(x): it = iter(x) prev, res = next(it), [] while prev is not None: start = next(it, None) if prev + 1 == start: res.append(prev) elif res: yield list(res + [prev]) res = [] prev = start # Driver program l = [8, 9, 10, 7, 8, 1, 2, 3]print(list(groupSequence(l))) |
[[8, 9, 10], [7, 8], [1, 2, 3]]
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n), as two additional lists are created with a maximum size of n.
Approach #4 : Using itertools Python itertools provides operations like cycle and groupby which are used in this method. First we form another list ‘temp_list‘ using cycle. Cycle generates an infinitely repeating series of values. Then we group the temp_list accordingly using groupby operation and finally yield the desired output.
Python3
# Python3 program to Find groups # of strictly increasing numbers within from itertools import groupby, cycledef groupSequence(l): temp_list = cycle(l) next(temp_list) groups = groupby(l, key = lambda j: j + 1 == next(temp_list)) for k, v in groups: if k: yield tuple(v) + (next((next(groups)[1])), ) # Driver program l = [8, 9, 10, 7, 8, 1, 2, 3]print(list(groupSequence(l))) |
[(8, 9, 10), (7, 8), (1, 2, 3)]
Approach #5: Using recursion
This approach uses recursion to find groups of strictly increasing numbers. The function find_groups takes two arguments – the input list and the index of the current element being processed. Initially, the index is set to 0. The function returns a list of lists, where each inner list represents a group of strictly increasing numbers.
Algorithm:
- If the index is equal to the length of the input list, return an empty list.
- Initialize the current element to the value at the current index.
- Find the groups of strictly increasing numbers starting from the next index recursively.
- If the next group starts with the current element + 1, add the current element to the start of the next group.
- If the next group is empty or does not start with the current element + 1, create a new group starting with the current element.
- Return the list of groups.
Python3
def find_groups(l, index=0): if index == len(l): return [] current_element = l[index] groups = find_groups(l, index + 1) if len(groups) > 0 and groups[0][0] == current_element + 1: groups[0].insert(0, current_element) else: groups.insert(0, [current_element]) return groups# Driver programl = [8, 9, 10, 7, 8, 1, 2, 3]print(find_groups(l)) |
[[8, 9, 10], [7, 8], [1, 2, 3]]
Time complexity: O(n^2), where n is the length of the input list. This is because in the worst case, we may have to check each element against every other element.
Auxiliary space: O(n), where n is the length of the input list. This is because we are creating a list of lists to store the groups.
