Given a 1D list ‘lst’ and list of variable lengths ‘var_lst’, write a Python program to convert the given 1D list to 2D list of given variable lengths. Examples:
Input : lst = [1, 2, 3, 4, 5, 6]
var_lst = [1, 2, 3]
Output : [[1], [2, 3], [4, 5, 6]]
Input : lst = ['a', 'b', 'c', 'd', 'e']
var_lst = [3, 2]
Output : [['a', 'b', 'c'], ['d', 'e']]
Method #1: List slicing
Python3
# Python3 program to Convert 1D # list to 2D listfrom itertools import islicedef convert(lst, var_lst): idx = 0 for var_len in var_lst: yield lst[idx : idx + var_len] idx += var_len # Driver codelst = [1, 2, 3, 4, 5, 6]var_lst = [1, 2, 3]print(list(convert(lst, var_lst))) |
[[1], [2, 3], [4, 5, 6]]
Time Complexity: O(n), where n is the length of the list
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the list
Method #2 : Using itertools.islice()
Python3
# Python3 program to Convert 1D # list to 2D listfrom itertools import islicedef convert(lst, var_lst): it = iter(lst) return [list(islice(it, i)) for i in var_lst] # Driver codelst = [1, 2, 3, 4, 5, 6]var_lst = [1, 2, 3]print(convert(lst, var_lst)) |
[[1], [2, 3], [4, 5, 6]]
Approach 3: Using recursion
This approach involves writing a recursive function that takes in the lst and var_lst as well as an optional start_idx parameter. The base case occurs when the var_lst is empty, in which case the function returns an empty list. Otherwise, the function returns a sublist of lst with length equal to the first element in var_lst concatenated with a recursive call to the function with the remaining elements of lst and var_lst.
Python3
def convert(lst, var_lst, start_idx=0): """ Convert a 1D list to a 2D list of variable length. Parameters: - lst: list[int] - 1D list to convert - var_lst: list[int] - list of lengths for each sublist in the 2D list - start_idx: int (optional) - starting index for slicing lst. Default is 0. Returns: - list[list[int]] - 2D list of variable length """ # Base case: return empty list when var_lst is empty if not var_lst: return [] # Recursive case: slice lst and make recursive call var_len = var_lst[0] sublist = lst[start_idx:start_idx+var_len] two_d_lst = [sublist] + convert(lst, var_lst[1:], start_idx+var_len) return two_d_lst# Test inputlst = [1, 2, 3, 4, 5, 6]var_lst = [1, 2, 3]print(convert(lst, var_lst))#This code is contributed by Edula Vinay Kumar Reddy |
[[1], [2, 3], [4, 5, 6]]
This function has a time complexity of O(n), where n is the length of the 1D list lst, since the function makes a single pass through lst and var_lst. The auxiliary space is also O(n), as the function creates a new sublist for each element in lst and stores it in two_d_lst.
Approach#4: using while loop
In this approach, we use a while loop to iterate through the list of variable lengths, and use slicing to extract the corresponding elements from the original list and append them to a new list.
Algorithm
- Initialize an empty 2D list called result.
- Initialize a variable called index to 0.
- Initialize a variable called i to 0.
- While i is less than the length of var_lst:
- Extract the sublist of var_lst[i] elements starting at index from lst using slicing.
- Append the sublist to result.
- Update index to index + var_lst[i].
- Increment i.
- Return result.
Python3
def convert_to_2d_list(lst, var_lst): result = [] index = 0 i = 0 while i < len(var_lst): sublist = lst[index:index+var_lst[i]] result.append(sublist) index += var_lst[i] i += 1 return resultlst = [1, 2, 3, 4, 5, 6]var_lst = [1, 2, 3]print(convert_to_2d_list(lst, var_lst)) |
[[1], [2, 3], [4, 5, 6]]
Time Complexity: O(N), where N is the length of the original list.
Space Complexity: O(N), where N is the length of the original list.
METHOD 5:Using defaultdict: This solution uses a defaultdict to create a dictionary of sublists from a given input list lst and a list of variable lengths var_lst. It then extracts the sublists from the dictionary in the order of var_lst and returns them as a list of lists.
- Create an empty defaultdict d.
- Initialize a variable start to 0.
- For each variable length var in var_lst, do the following:
- Compute the end index end as start + var.
- Slice the sublist lst[start:end] from last.
- Append the sublist to the list at key var in d.
- Update from start to end.
- Initialize an empty list result.
- For each variable length var in var_lst, do the following:
- Remove the first sublist from the list at key var in d using pop(0).
- Append the sublist to the result.
- Return result.
Python3
from collections import defaultdictlst = [1, 2, 3, 4, 5, 6]var_lst = [1, 2, 3]# Use defaultdict to create a# dictionary of sublistsd = defaultdict(list)start = 0for var in var_lst: end = start + var d[var].append(lst[start:end]) start = end# Extract the sublists from the# dictionary in the order of var_lstresult = [d[var].pop(0) for var in var_lst]print(result) |
[[1], [2, 3], [4, 5, 6]]
Time Complexity: The time complexity of this solution is O(n), where n is the length of the input list lst. This is because the solution iterates over lst once to create the dictionary of sublists, and then iterates over var_lst once to extract the sublists from the dictionary.
Space Complexity: The space complexity of this solution is O(n), where n is the length of the input list lst. This is because the solution creates a dictionary of sublists that can potentially contain all n elements of lst, as well as a list result that contains all the sublists in the correct order.
Approach#5: Using Numpy
In this approach, we use the numpy library to convert the given 1D list to a numpy array and then use the cumsum() function to get the indices where we need to split the array to get the desired 2D list. We then use slicing to split the array and convert the resulting arrays back to a list.
Algorithm
- Convert the 1D list to a numpy array.
- Calculate the cumulative sum of the variable lengths list.
- Use slicing to split the array at the indices obtained in step 2.
- Convert the resulting arrays back to a list and return the 2D list.
Python3
import numpy as npdef convert_to_2d_list(lst, var_lst): # Convert the list to a numpy array arr = np.array(lst) # Calculate the cumulative sum of the variable lengths list cum_sum = np.cumsum(var_lst) # Split the array at the indices obtained from the cumulative sum result_arr = np.split(arr, cum_sum) # Convert the resulting arrays back to a list result = [list(subarr) for subarr in result_arr][:-1] return result# Example usagelst = ['a', 'b', 'c', 'd', 'e']var_lst = [3, 2]print(convert_to_2d_list(lst, var_lst)) |
Output: [['a', 'b', 'c'], ['d', 'e']]
Time Complexity:
Converting the list to a numpy array takes O(n) time, where n is the length of the list. Calculating the cumulative sum takes O(m) time, where m is the length of the variable lengths list. Splitting the array takes O(m) time as well. Finally, converting the resulting arrays back to a list takes O(mn) time, where n is the length of the original list. Therefore, the total time complexity of the function is O(mn).
Space Complexity:
Converting the list to a numpy array takes O(n) space. Calculating the cumulative sum takes O(m) space as well. Splitting the array and converting the resulting arrays back to a list both take O(mn) space. Therefore, the total space complexity of the function is O(mn).
