Given a list, extract a range of consecutive similar elements.
Input : test_list = [2, 3, 3, 3, 8, 8] Output : [(2, 0, 0), (3, 1, 3), (8, 4, 5)] Explanation : 2 occurs from 0th to 0th index, 3 from 1st to 3rd index.
Input : test_list = [3, 3, 3] Output : [(3, 0, 3)] Explanation : 3 from 0th to 3rd index.
Approach: Using loop
This is a brute way to tackle this problem. In this, we loop for each element and get a similar element range. These are traced and appended in the list accordingly with elements.
Steps:
- Initialize a list test_list with integer values.
- Print the original list.
- Initialize an empty list res to store the results.
- Initialize a variable idx to 0.
- While the value of idx is less than the length of the test_list:
a. Set the variable strt_pos equal to the current value of idx.
b. Set the variable val equal to the value at index idx in test_list.
c. While the value of idx is less than the length of test_list and the value at index idx is equal to val, increment idx by 1.
d. Set the variable end_pos equal to idx – 1.
e. Append the tuple (val, strt_pos, end_pos) to the list res. - Print the elements with their range in the format [ele, strt_pos, end_pos] using the res list.
Python3
# Python3 code to demonstrate working of# Consecutive Similar elements ranges# Using loop# Initializing listtest_list = [2, 3, 3, 3, 8, 8, 6, 7, 7]# Printing original listprint("The original list is : " + str(test_list))res = []idx = 0while idx < (len(test_list)): strt_pos = idx val = test_list[idx] # Getting last position while (idx < len(test_list) and test_list[idx] == val): idx += 1 end_pos = idx - 1 # Appending in format [element, start, end position] res.append((val, strt_pos, end_pos))# Printing resultprint("Elements with range : " + str(res)) |
Output
The original list is : [2, 3, 3, 3, 8, 8, 6, 7, 7] Elements with range : [(2, 0, 0), (3, 1, 3), (8, 4, 5), (6, 6, 6), (7, 7, 8)]
Time Complexity: O(n2)
Auxiliary Space: O(n)
Method 2: using Python’s built-in itertools.groupby() function
Approach:
- Import itertools module.
- Initialize the list.
- Use groupby() function to group the elements based on their value.
- Convert the groupby object to a list of tuples and store them in res.
- For each tuple in res, extract the key (i.e., the value of the similar elements), the start index, and the end index using the built-in functions.
- Append a tuple of (key, start index, end index) to the result list.
- Print the original list and the elements with their range.
Python3
# Python3 code to demonstrate working of# Consecutive Similar elements ranges# Using Python's built-in itertools.groupby() methodimport itertools# Initializing listtest_list = [2, 3, 3, 3, 8, 8, 6, 7, 7]# Printing original listprint("The original list is : " + str(test_list))# Grouping similar elements# using itertools.groupby() methodres = []for k, g in itertools.groupby(test_list): group = list(g) start_index = test_list.index(group[0]) end_index = start_index + len(group) - 1 res.append((k, start_index, end_index))# Printing the resultprint("Elements with range : " + str(res)) |
Output
The original list is : [2, 3, 3, 3, 8, 8, 6, 7, 7] Elements with range : [(2, 0, 0), (3, 1, 3), (8, 4, 5), (6, 6, 6), (7, 7, 8)]
Time Complexity: O(n), where n is the length of the list.
Auxiliary Space: O(n), to store the result list.
Method 3: Using the numpy library
Step-by-step approach:
- Import the numpy library.
- Convert the given list to a numpy array using numpy.array() method.
- Calculate the difference between consecutive elements using the numpy.diff() method and concatenate a 0 at the beginning to capture the starting index of each group.
- Find the indices where the difference is non-zero using the numpy.nonzero() method.
- Calculate the start and end indices for each group by iterating through the indices obtained in step 4.
- Create a list of tuples containing the group value and its start and end indices.
- Return the resulting list.
Python3
import numpy as npdef consecutive_similar_elements_ranges(test_list): # Convert list to numpy array arr = np.array(test_list) # Calculate difference between consecutive elements diff = np.concatenate(([0], np.diff(arr))) # Find indices where difference is non-zero idx = np.nonzero(diff)[0] # Iterate through indices and calculate start and end indices for each group res = [] for i in range(len(idx)): start = idx[i] end = idx[i+1]-1 if i+1 < len(idx) else len(test_list)-1 res.append((test_list[start], start, end)) # Check if the first element is missing from the result if len(res) == 0 or res[0][0] != test_list[0]: res.insert(0, (test_list[0], 0, 0)) return res# Example usagetest_list = [2, 3, 3, 3, 8, 8, 6, 7, 7]print(consecutive_similar_elements_ranges(test_list)) |
OUTPUT : [(2, 0, 0), (3, 1, 3), (8, 4, 5), (6, 6, 6), (7, 7, 8)]
Time complexity: O(n), where n is the length of the input list.
Space complexity: O(n), where n is the length of the input list.
