Python – Extract rows with Even length strings

In this article, we have a given Matrix, and extract rows that are of even lengths.

Input : test_list = [["gfg", "is", "best"], ["best", "good", "geek"], 
                    ["is", "better"], ["for", "cs"]] 
Output : [['best', 'good', 'geek'], ['is', 'better']] 
Explanation : All strings are of even length.

Input : test_list = [["gfg", "is", "best"], ["best", "good", "neveropen"], 
                    ["is", "better"], ["for", "cs"]] 
Output : [['is', 'better']] 
Explanation : All strings are of even length. 

Method #1 : Using all() + list comprehension + len()

In this, we check for all the strings in each row, and their length, and check if the length is even, if all strings in the row have an even length, then it’s added to the result list.

Time Complexity: O(n*n)
Auxiliary Space: O(1)

Method #2 : Using filter() + lambda + len()

In this, we perform the task of filtering using filter() + lambda, len() as in the above method, which performs the task of getting the length of each string.

Time Complexity: O(n) where n is the number of elements in the list “test_list”.  filter() and lambda function performs n number of operations.
Auxiliary Space: O(1), no extra space is required

Method #3: Using a for loop

1. Start by initializing an empty list to store the even-length rows.
2. Iterate over each row in the input list using a loop.
3. For each row, iterate over each element in the row using another loop.
4. Check if the length of the current element is even or not using an if statement and the modulus operator.
5. If the length is odd, break out of the inner loop and move on to the next row.
6. If all the elements in the current row have even length, append the row to the list of even-length rows.
7. Once all rows have been processed, return the list of even-length rows.

The original list is : [['gfg', 'is', 'best'], ['best', 'good', 'geek'], ['is', 'better'], ['for', 'cs']]
Rows with even length : [['best', 'good', 'geek'], ['is', 'better']]

Time complexity: O(n*m) where n is the number of rows and m is the maximum number of elements in a row.
Auxiliary space: O(k) where k is the number of even-length rows in the list.

Method #4:Using the reduce() function and a lambda function:

Steps:

1. Initialize an empty list ‘res’ to store rows with even length strings.
2. Use reduce() function to iterate through the list of lists and apply a lambda function to each row.
3. The lambda function checks if all elements in the row have an even length, and if so, it adds the row to the accumulator list.
4. Return the accumulator list.

The original list is : [['gfg', 'is', 'best'], ['best', 'good', 'geek'], ['is', 'better'], ['for', 'cs']]
Rows with even length : [['best', 'good', 'geek'], ['is', 'better']]

Time complexity:
The time complexity of this code is O(n*m), where n is the number of lists and m is the maximum length of a list. This is because we need to iterate through each element in each list to check its length.

Auxiliary Space:
The space complexity of this code is O(k), where k is the number of rows with even length strings. This is because we are storing each row that meets the criteria in a new list ‘res’. The reduce() function does not create any additional space complexity, as it operates on the existing list of lists without creating a new list.

Method #5: Using heapq

Algorithm:

1. Initialize an empty heap and a result list.
2. For each row in the input list, create a tuple with the length of the row and the row itself.
3. Add each tuple to the heap.
4. Using heapq, extract the rows with the largest length.
5. For each row with a large length, check if all elements in the row have even length.
6. If so, add the row to the result list.
7. Return the result list.

The original list is : [['gfg', 'is', 'best'], ['best', 'good', 'geek'], ['is', 'better'], ['for', 'cs']]
Rows with even length : [['best', 'good', 'geek'], ['is', 'better']]

Time Complexity: O(NlogN * M)

Creating the heap requires traversing the entire input list once, which takes O(n) time.
Extracting the rows with the largest length using heapq requires traversing the heap once, which takes O(nlogn) time. Checking if all elements in each row have even length requires traversing the row once, which takes O(m) time, where m is the length of the row. Therefore, the overall time complexity is O(nlogn * m).

Auxiliary Space: O(N)

Creating the heap requires storing a tuple for each row, which takes O(n) space.
The result list can also take up to O(n) space in the worst case.
Therefore, the overall space complexity is O(n).

Method 6: Using a nested list comprehension +  all() function

1. Initialize the test_list with the given list of lists.
2. Use a list comprehension to iterate over each row in the test_list.
3. Check if all the words in the current row have even length. Use another list comprehension to iterate over the words in the current row and check if the length of each word is even.
4. If all the words in the current row have even length, include the current row in the res_list.
5. Print the res_list which contains all the rows from the test_list that have only words with even length.

Rows with even length: [['best', 'good', 'geek'], ['is', 'better']]

Time complexity: O(n*m), where n is the number of rows and m is the maximum number of words in a row, and an Auxiliary space: O(1), as it only requires a few temporary variables.