Python List Advanced Exercise - First non-repeated element in a list

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

Write a Python program to find the first non-repeated element in a list.

Sample Solution:

Python Code:

# Define a function to find the first non-repeated element in a list
def first_non_repeated_el(lst):
    # Create a dictionary 'ctr' to count the occurrences of each element
    ctr = {}
    # Iterate through the elements in the list
    for i in lst:
        # If the element is already in the dictionary, increment its count
        if i in ctr:
            ctr[i] += 1
        # If the element is not in the dictionary, add it with a count of 1
        else:
            ctr[i] = 1
    # Iterate through the elements in the list again
    for i in lst:
        # Find the first element with a count of 1 (non-repeated)
        if ctr[i] == 1:
            return i
    # If no non-repeated element is found, return None

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

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

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

# Print the result, which is the first non-repeated element in the list
print("First non-repeated element in the said list:")
print(result)

# Create another list of numbers with some repeated elements
nums =  [1, 2, 3, 1, 2, 4, 5, 6, 7, 8]

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

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

# Print the result, which is the first non-repeated element in the list
print("First non-repeated element in the said list:")
print(result)

# Create another list of numbers with more repeated elements
nums =  [1, 1, 2, 3, 1, 2, 3, 8, 8]

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

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

# Print the result, which is the first non-repeated element in the list
print("First non-repeated element in the said list:")
print(result) 

Sample Output:

Original list:
[1, 2, 3, 4, 5, 6, 7, 8]
First non-repeated element in the said list:
1

Original list:
[1, 2, 3, 1, 2, 4, 5, 6, 7, 8]
First non-repeated element in the said list:
3

Original list:
[1, 1, 2, 3, 1, 2, 3, 8, 8]
First non-repeated element in the said list:
None

Flowchart:

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

def first_non_repeated_el(lst):
    ctr = {}
    for i in lst:
        if i in ctr:
            ctr[i] += 1
        else:
            ctr[i] = 1
    for i in lst:
        if ctr[i] == 1:
            return i
    return None

Time complexity - The time complexity of the said code is O(n), where n is the length of the input list "lst". This is because the code iterates through "lst" twice, and each iteration takes O(n) time in the worst case. The first iteration populates a dictionary "ctr" with the count of occurrences of each element in "lst". Since the dictionary “ctr” has at most n distinct keys, inserting or updating a key takes constant time on average. Therefore, the first iteration takes O(n) time. The second iteration checks each element of "lst" to see if it has a count of 1 in ctr. Since checking for a key in a dictionary takes constant time on average, the second iteration also takes O(n) time. Therefore, 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 dictionary "ctr" with at most n distinct keys, each of which takes constant space on average. Therefore, the space complexity of "ctr" is O(n). The rest of the space used by the code is proportional to the size of the input list "lst", which is also O(n). Therefore, the overall space complexity is O(n).

Python Code Editor:

Previous: Longest common sub-sequence in two lists.
Next: Implement a LRU cache.