Given a List, extract K elements occurring in middle of list.
Input : test_list = [2, 3, 5, 7, 8, 5, 3, 5, 9], K = 3
Output : [7, 8, 5]
Explanation : Middle 3 elements are extracted.Input : test_list = [2, 3, 5, 7, 8, 5, 3, 5, 9], K = 7
Output : [3, 5, 7, 8, 5, 3, 5]
Explanation : Middle 7 elements are extracted.
Method #1: Using loop
In this, we initially formulate the range, extracting half pre middle, and half post middle elements, and then use a loop to extract desired elements. Works evenly in odd length lists.
Python3
# Python3 code to demonstrate working of # K middle elements# Using loop# initializing listtest_list = [2, 3, 5, 7, 8, 5, 3, 5, 9]# printing original listprint("The original list is : " + str(test_list))# initializing K K = 5# computing strt, and end index strt_idx = (len(test_list) // 2) - (K // 2)end_idx = (len(test_list) // 2) + (K // 2)# using loop to get indices res = []for idx in range(len(test_list)): # checking for elements in range if idx >= strt_idx and idx <= end_idx: res.append(test_list[idx])# printing result print("Extracted elements list : " + str(res)) |
The original list is : [2, 3, 5, 7, 8, 5, 3, 5, 9] Extracted elements list : [5, 7, 8, 5, 3]
Time Complexity: O(n) where n is the number of elements in the list “test_list”. we’re iterating through the list
Auxiliary Space: O(n), extra space is required where n is the number of elements in the list
Method #2: Using list slicing
In this, after range computation step, the range extraction occurs using list slicing.
Python3
# Python3 code to demonstrate working of # K middle elements# Using list slicing # initializing listtest_list = [2, 3, 5, 7, 8, 5, 3, 5, 9]# printing original listprint("The original list is : " + str(test_list))# initializing K K = 5# computing strt, and end index strt_idx = (len(test_list) // 2) - (K // 2)end_idx = (len(test_list) // 2) + (K // 2)# slicing extracting middle elementsres = test_list[strt_idx: end_idx + 1]# printing result print("Extracted elements list : " + str(res)) |
The original list is : [2, 3, 5, 7, 8, 5, 3, 5, 9] Extracted elements list : [5, 7, 8, 5, 3]
Method#3: Using list comprehension
Algorithm:
- Initialize the input list and K.
- Calculate the middle index of the input list.
- Calculate the starting and ending indices of the middle K range.
- Use list comprehension to extract the elements within the middle K range.
- Print the extracted elements list.
Python3
# initializing the test listtest_list = [2, 3, 5, 7, 8, 5, 3, 5, 9]# initializing the value of KK = 5# calculating the middle index of the listmiddle = len(test_list) // 2# using list comprehension to extract the middle K elements# we iterate over the range of indices that fall within the middle K range# and extract the corresponding elements from the list# the middle - K//2 and middle + (K//2) + 1 are used to compute the starting and ending indicesres = [test_list[i] for i in range(middle - K//2, middle + (K//2) + 1)]# printing the extracted elements listprint("Extracted elements list : " + str(res)) |
Extracted elements list : [5, 7, 8, 5, 3]
Time Complexity:
The time complexity of this approach is O(K), where K is the number of elements to be extracted. The list comprehension iterates over K elements to extract the corresponding elements from the input list.
Auxiliary Space Complexity:
The auxiliary space complexity of this approach is O(K), where K is the number of elements to be extracted. This is because we are creating a new list to store the extracted elements, which can have at most K elements
Method 4 : using the heapq.nsmallest() function from the heapq module.
Importing the heapq module.
Initializing a test list with integer values.
Initializing the value of K.
Calculating the middle index of the test list by dividing the length of the test list by 2 and rounding down to the nearest integer using the floor division operator (//).
Using the heapq.nsmallest() method to extract the middle K elements from the test list.
The heapq.nsmallest() method takes two arguments – the first argument is the number of smallest elements to extract (in this case, K), and the second argument is the list to extract the elements from (in this case, a slice of the test list starting from the index middle-K//2 and ending at the index middle+K//2+1).
The expression middle-K//2 calculates the starting index for the slice, and the expression middle+K//2+1 calculates the ending index for the slice. The // operator performs floor division, which ensures that the starting and ending indices are integers.
The extracted elements are stored in the variable res.
The extracted elements list is printed to the console using the print() function, along with a string that describes the output.
Python3
import heapq# initializing the test listtest_list = [2, 3, 5, 7, 8, 5, 3, 5, 9]# initializing the value of KK = 5# calculating the middle index of the listmiddle = len(test_list) // 2# using heapq.nsmallest() to extract the middle K elementsres = heapq.nsmallest(K, test_list[middle-K//2:middle+K//2+1])# printing the extracted elements listprint("Extracted elements list: " + str(res)) |
Extracted elements list: [3, 5, 5, 7, 8]
The time complexity is O(KlogK) because heapq.nsmallest() uses a heap data structure, which has a time complexity of O(logK) to add an element and O(1) to remove the smallest element.
The auxiliary space complexity is O(K) to store the extracted elements in a list.
