Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in Python

Solution: Remove Even Integers From List

Explore how to remove even integers from a list by applying Python list traversal and list comprehension techniques. Understand the solutions' time complexity of O(n) and space efficiency of O(1), helping you implement clear and efficient list manipulations.

We'll cover the following...

Statement

Given a list of integers, lst, remove all the even integers from the list.

Constraints:

  • 1≤1 \leq lst.length ≤103\leq 10^3
  • −105≤-10^5 \leq lst[i] ≤105\leq 10^5

Solution 1: Using list traversal

The naive approach is to traverse the list and add all the odd integers to a separate list. This results in a new list, with all the even integers removed.

Here are the steps of this solution:

  1. Initialize a new list, odds.

  2. Traverse through lst, and for each element in the list:

    1. Append the current element to the odds list if it’s an odd integer (i.e., not divisible by 2).

  3. Finally, return odds after all elements of lst are traversed.

Let’s look at the illustration below to better understand the solution:

canvasAnimation-image
1 / 9

Let’s look at the code for this solution below:

Python 3.10.4
def remove_even(lst):
    odds = []
    for number in lst:  
        # Check if the item in the list is not even
        if number % 2 != 0:
            odds.append(number)  # // If it isn't even, append it to the odds list
    return odds
def main():
    inputs = [
            [3, 2, 41, 3, 34],
            [-5, -4, -3, -2, -1],
            [-1, 2, 3, -4, -10],
            [1, 2, 3, 7],
            [2, 4, 6, 8, 10],
    ]
    for i in range(len(inputs)):
        print(i + 1, ".\tInput list: ", inputs[i], sep="")
        print("\n\tFinal list: ", remove_even(inputs[i]), sep="")
        print("-" * 100)
if __name__ == "__main__":
    main()

Complexity analysis

Let’s look at the time and space complexity of this solution:

Time complexity

The time complexity of the solution is O(n)O(n) because the input list is traversed once, where nn is the number of elements in the list.

Space complexity

The space complexity is O(1)O(1) because no extra space is used.

Solution 2: Using list comprehension

The solution above can be made further readable using Python list comprehension.

List comprehension is a concise way to create lists in Python. It allows for the generation of new lists by applying an expression to each item in a sequence or iterable, optionally filtering items under a specified condition. The general syntax of a list comprehension is:

[new_expression for item in iterable if condition]
  • new_expression: This is the expression that defines how each item in the new list should be constructed from the items in the original iterable.
  • item: This represents the current element during each iteration through the iterable.
  • iterable: This is the collection of elements that the list comprehension iterates over.
  • condition: This is an optional part that if provided, tests each item in the iterable to decide if it should be included in the new list.

Let’s look at the code for this solution below:

Python 3.10.4
def remove_even(lst):
    # List comprehension to iterate over list and add to a new list if not even
    return [number for number in lst if number % 2 != 0]
def main():
    inputs = [
            [3, 4, 40, 31, 32],
            [-5, -4, -6, -2, -3],
            [-1, 2, 5, -4, -10],
            [1],
            [2, 4, 6, 8, 10],
    ]
    for i in range(len(inputs)):
        print(i + 1, ".\tInput list: ", inputs[i], sep="")
        print("\n\tFinal list: ", remove_even(inputs[i]), sep="")
        print("-" * 100)
if __name__ == "__main__":
    main()

Complexity analysis

Let’s look at the time and space complexity of this solution:

Time complexity

Using list comprehension enhances code readability. However, the time complexity remains O(n)O(n) because we still need to traverse the entire input list to determine whether an integer is odd.

Space complexity

The space complexity is O(1)O(1) because no extra space is used.