Python List Advanced Exercise - Preserve order by removing duplicates

Last update on December 21 2024 07:34:03 (UTC/GMT +8 hours)

Write a Python function to remove duplicates from a list while preserving the order.

Sample Solution-1:

Python Code:

# Import the OrderedDict class from the collections module
from collections import OrderedDict

# Define a function to remove duplicates from a list while preserving the order
def remove_duplicates(lst):
    # Use OrderedDict to create a dictionary with the list elements as keys (preserves order)
    # Then, convert it back to a list to remove duplicates
    return list(OrderedDict.fromkeys(lst))

# Create a list of numbers
nums = [1, 2, 4, 3, 5, 4, 6, 9, 2, 1]

# Print the original list of numbers
print("Original list:")
print(nums)

# Call the remove_duplicates function with the list and store the result in 'result'
result = remove_duplicates(nums)

# Print the result, which is the list with duplicates removed while preserving order
print("Remove duplicates from the said list while preserving the order:")
print(result)

# Create a list of characters
chars = ['a', 'a', 'b', 'a', 'a', 'c', 'c', 'c', 'd', 'e', 'a', 'b', 'b', 'b']

# Print the original list of characters
print("\nOriginal list:")
print(chars)

# Call the remove_duplicates function with the character list and store the result in 'result'
result = remove_duplicates(chars)

# Print the result, which is the list with duplicates removed while preserving order
print("Remove duplicates from the said list while preserving the order:")
print(result) 

Sample Output:

Original lists:
[1, 2, 4, 3, 5, 4, 6, 9, 2, 1]
Remove duplicates from the said list while preserving the order:
[1, 2, 4, 3, 5, 6, 9]

Original lists:
['a', 'a', 'b', 'a', 'a', 'c', 'c', 'c', 'd', 'e', 'a', 'b', 'b', 'b']
Remove duplicates from the said list while preserving the order:
['a', 'b', 'c', 'd', 'e']

Flowchart:

What is the time complexity and space complexity of the following Python code?

from collections import OrderedDict
def remove_duplicates(lst):
    return list(OrderedDict.fromkeys(lst))

Time complexity - The time complexity of this code is O(n), where n is the length of the input list "lst". The Python OrderedDict.fromkeys() method removes duplicates from the input list (here "lst") while preserving the order of the remaining elements. This method has a time complexity of O(n) in the worst case because it needs to iterate over every element in the list.
The list() method is used to convert the resulting OrderedDict.fromkeys(lst) back to a list, which takes O(n) time in the worst case.

Space complexity - The space complexity of this code is also O(n), since a new OrderedDict object is created to store the unique elements of the input list "lst". The OrderedDict object uses a hash table to store the keys and their corresponding values, which can take up to O(n) space in the worst case if there are no duplicates in the input list. In addition, a new list is created to store the unique elements of the input list "lst", which also takes up O(n) space.

Sample Solution-2:

Python Code:

# Define a function to remove duplicates from a list while preserving the order
def remove_duplicates(lst):
    # Create a dictionary from the list, which automatically removes duplicates
    # Then, convert the keys of the dictionary back to a list to preserve order
    return list(dict.fromkeys(lst).keys())

# Create a list of numbers
nums = [2, 4, 3, 5, 4, 6, 9, 2, 1]

# Print the original list of numbers
print("Original list:")
print(nums)

# Call the remove_duplicates function with the list and store the result in 'result'
result = remove_duplicates(nums)

# Print the result, which is the list with duplicates removed while preserving order
print("Remove duplicates from the said list while preserving the order:")
print(result)

# Create a list of characters
chars = ['b', 'a', 'a', 'c', 'c', 'c', 'd', 'e', 'a', 'b', 'b', 'b']

# Print the original list of characters
print("\nOriginal list:")
print(chars)

# Call the remove_duplicates function with the character list and store the result in 'result'
result = remove_duplicates(chars)

# Print the result, which is the list with duplicates removed while preserving order
print("Remove duplicates from the said list while preserving the order:")
print(result) 

Sample Output:

Original lists:
[2, 4, 3, 5, 4, 6, 9, 2, 1]
Remove duplicates from the said list while preserving the order:
[2, 4, 3, 5, 6, 9, 1]

Original lists:
['b', 'a', 'a', 'c', 'c', 'c', 'd', 'e', 'a', 'b', 'b', 'b']
Remove duplicates from the said list while preserving the order:
['b', 'a', 'c', 'd', 'e']

Flowchart:

What is the time complexity and space complexity of the following Python code?

def remove_duplicates(lst):
    return list(dict.fromkeys(lst).keys())

Time complexity - The time complexity of the given code is O(n), where n is the length of the input list "lst". This is because the dict.fromkeys() method creates a dictionary with keys equal to the unique elements of "lst", which takes O(n) time. Then, the keys() method is called on the resulting dictionary to get a list of unique elements, which also takes O(n) time. So, the overall time complexity is O(n).

Space complexity - The space complexity of the given code is O(n), where n is the length of the input list "lst". This is because the code creates a new dictionary with keys equal to the unique elements of "lst", which has space complexity proportional to the number of unique elements. In the worst case where all elements of list "lst" are unique, the dictionary will have length n, giving O(n) space complexity. The keys() method returns a list of unique elements, which also has space complexity proportional to the number of unique elements. Therefore, the overall space complexity is O(n).

Python Code Editor:

Previous: Check if a list is a palindrome or not.
Next: Maximum sum sub-sequence in a list.