Python - K difference index pairing in list
Last Updated :
18 Apr, 2023
Sometimes while programming, we can face a problem in which we need to perform K difference element concatenation. This problem can occur at times of school programming or competitive programming. Let’s discuss certain ways in which this problem can be solved.
Method #1 : Using list comprehension + zip() Combination of above functionalities can be used to solve this problem. In this, we iterate the list using list comprehension and formation of pairs using zip().
Python3
# Python3 code to demonstrate working of
# K difference index pairing in list
# using list comprehension + zip()
# initialize list
test_list = ["G", "F", "G", "I", "S", "B", "E", "S", "T"]
# printing original list
print("The original list : " + str(test_list))
# initialize K
K = 3
# K difference index pairing in list
# using list comprehension + zip()
res = [i + j for i, j in zip(test_list, test_list[K :])]
# printing result
print("List after K difference concatenation is : " + str(res))
Output : The original list : ['G', 'F', 'G', 'I', 'S', 'B', 'E', 'S', 'T']
List after K difference concatenation is : ['GI', 'FS', 'GB', 'IE', 'SS', 'BT']
Time Complexity: O(n*n) where n is the number of elements in the list “test_list”. list comprehension + zip() performs n*n number of operations.
Auxiliary Space: O(n), extra space is required where n is the number of elements in the list
Method #2 : Using map() + concat() The combination of these functions can also perform this task. In this traversal logic is done by map() and concat performs the task of pairing. It’s more efficient than above method.
Python3
# Python3 code to demonstrate working of
# K difference index pairing in list
# using map() + concat
import operator
# initialize list
test_list = ["G", "F", "G", "I", "S", "B", "E", "S", "T"]
# printing original list
print("The original list : " + str(test_list))
# initialize K
K = 3
# K difference index pairing in list
# using map() + concat
res = list(map(operator.concat, test_list[:-1], test_list[K:]))
# printing result
print("List after K difference concatenation is : " + str(res))
Output : The original list : ['G', 'F', 'G', 'I', 'S', 'B', 'E', 'S', 'T']
List after K difference concatenation is : ['GI', 'FS', 'GB', 'IE', 'SS', 'BT']
Time Complexity: O(n*n), where n is the length of the input list. This is because we’re using map() + concat() which has a time complexity of O(n*n) in the worst case.
Auxiliary Space: O(n), as we’re using additional space res other than the input list itself with the same size of input list
Method #3 : Using join()
This is the most efficient method as it uses the combination of zip and join functions to perform this task.
Python3
# Python3 code to demonstrate working of
# K difference index pairing in list
# using zip() + join()
# initialize list
test_list = ["G", "F", "G", "I", "S", "B", "E", "S", "T"]
# printing original list
print("The original list : " + str(test_list))
# initialize K
K = 3
# K difference index pairing in list
# using zip() + join()
res = list(map("".join, zip(test_list, test_list[K:])))
# printing result
print("List after K difference concatenation is : " + str(res))
#This code is contributed by Edula Vinay Kumar Reddy
OutputThe original list : ['G', 'F', 'G', 'I', 'S', 'B', 'E', 'S', 'T']
List after K difference concatenation is : ['GI', 'FS', 'GB', 'IE', 'SS', 'BT']
Time complexity: O(n)
Auxiliary Space: O(n)
Method #4: Using Recursive method.
Python3
def K_difference_pairing(test_list, K):
if K >= len(test_list):
return []
if K == 1:
return [test_list[i]+test_list[i+1] for i in range(len(test_list)-1)]
return [test_list[0]+test_list[K]] + K_difference_pairing(test_list[1:], K)
# initialize list
test_list = ["G", "F", "G", "I", "S", "B", "E", "S", "T"]
# printing original list
print("The original list : " + str(test_list))
# initialize K
K = 3
# K difference index pairing in list
res = K_difference_pairing(test_list, K)
# printing result
print("List after K difference concatenation is : " + str(res))
#this code contributed by tvsk
OutputThe original list : ['G', 'F', 'G', 'I', 'S', 'B', 'E', 'S', 'T']
List after K difference concatenation is : ['GI', 'FS', 'GB', 'IE', 'SS', 'BT']
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #5: Using a loop to iterate over the list
Step-by-step approach:
- Initialize an empty list to store the result.
- Use a for loop to iterate over the indices of the list from 0 to len(test_list) - K.
- For each index i, append the concatenation of test_list[i] and test_list[i+K] to the result list.
- Return the result list.
Below is the implementation of the above approach:
Python3
# Python3 code to demonstrate working of
# K difference index pairing in list
# using a loop
# initialize list
test_list = ["G", "F", "G", "I", "S", "B", "E", "S", "T"]
# printing original list
print("The original list : " + str(test_list))
# initialize K
K = 3
# K difference index pairing in list
# using a loop
res = []
for i in range(len(test_list) - K):
res.append(test_list[i] + test_list[i+K])
# printing result
print("List after K difference concatenation is : " + str(res))
OutputThe original list : ['G', 'F', 'G', 'I', 'S', 'B', 'E', 'S', 'T']
List after K difference concatenation is : ['GI', 'FS', 'GB', 'IE', 'SS', 'BT']
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.
Similar Reads
Python | Find Maximum difference pair
Sometimes, we need to find the specific problem of getting the pair which yields the maximum difference, this can be solved by sorting and getting the first and last elements of the list. But in some case, we don't with to change the ordering of list and perform some operation in a similar list with
5 min read
Python - Key Value list pairings in Dictionary
Sometimes, while working with Python dictionaries, we can have problems in which we need to pair all the keys with all values to form a dictionary with all possible pairings. This can have application in many domains including day-day programming. Lets discuss certain ways in which this task can be
7 min read
Python - Get minimum difference in Tuple pair
Sometimes, while working with data, we might have a problem in which we need to find minimum difference between available pairs in list. This can be application to many problems in mathematics domain. Let’s discuss certain ways in which this task can be performed.Method #1 : Using min() + list compr
4 min read
Python | Difference in Record Lists
Sometimes, while working with data, we may have a problem in which we require to find the difference records between two lists that we receive. This is a very common problem and records usually occurs as a tuple. Let’s discuss certain ways in which this problem can be solved. Method #1 : Using list
5 min read
Python | Consecutive elements pairing in list
This process involves creating pairs of elements that appear next to each other, which can be invaluable for various applications such as data analysis, pattern recognition and algorithm development. We can achieve this using different methods in Python, such as using simple loops, list slicing, zip
3 min read
Python - Sort from Kth index in List
Given a list of elements, perform sort from Kth index of List. Input : test_list = [7, 3, 7, 6, 4, 9], K = 2 Output : [7, 3, 4, 6, 7, 9] Explanation : List is unsorted till 3 (1st index), From 2nd Index, its sorted. Input : test_list = [5, 4, 3, 2, 1], K= 3 Output : [5, 4, 3, 1, 2] Explanation : Onl
3 min read
Python - Pair iteration in list
Pair iteration involves accessing consecutive or specific pairs of elements from a list. It is a common task particularly in scenarios such as comparing neighboring elements, creating tuple pairs, or analyzing sequential data. Python provides several ways to iterate through pairs efficiently ranging
2 min read
Python - Difference of List keeping duplicates
The problem of finding difference between list, i.e removing elements that occur in one list and not in other is discussed before. But the usage of sets ignores duplicates and we sometimes, require to remove the exact elements that occur in lists. Lets discuss certain ways in which this task can be
6 min read
Python - Element wise Matrix Difference
Given two Matrixes, the task is to write a Python program to perform element-wise difference. Examples: Input : test_list1 = [[2, 4, 5], [5, 4, 2], [1, 2, 3]], test_list2 = [[6, 4, 6], [9, 6, 3], [7, 5, 4]] Output : [[4, 0, 1], [4, 2, 1], [6, 3, 1]] Explanation : 6 - 2 = 4, 4 - 4 = 0, 6 - 5 = 1. And
3 min read
Python - Cross Pairing in Tuple List
Given 2 tuples, perform cross pairing of corresponding tuples, convert to single tuple if 1st element of both tuple matches. Input : test_list1 = [(1, 7), (6, 7), (8, 100), (4, 21)], test_list2 = [(1, 3), (2, 1), (9, 7), (2, 17)] Output : [(7, 3)] Explanation : 1 occurs as tuple element at pos. 1 in
5 min read