educative.io

Thoughts about using a list to keep values instead of using an outer and inner variables

Courses
,
#1

is this answer as good as the one proposed in the course? if not, why?

#remove duplicates from Linked List  
      def remove_duplicates(self):
                if self.is_empty():
                    return None

                if self.get_head().next_element is None:
                    return self.get_head()

                values = []

                current = self.get_head()
                values.append(current.data)

                prev = current 
                current = current.next_element

                while current:
                    if current.data in values:
                        prev.next_element = current.next_element
                        current.next_element = None
                        current = prev.next_element
                    else:
                        values.append(current.data)
                        prev = current
                        current = current.next_element

                return self.get_head()
#2

Hi @Luis_Daniel_Fonseca,

Your solution is correct and is as good as the one proposed in the course with regard to time complexity. If we go through your solution the time complexity is still O(n^2) as the search time for current.data in values is O(n). This combined with the while loop keeps the time complexity as O(n^2).

However, by using a list to store the values we increase the space complexity of the solution. It is later mentioned in the lesson that it is not the most optimal solution for this problem and by using Hashing we can achieve a time complexity of O(n). That solution would be:

def remove_duplicates(lst):
    current_node = lst.get_head()
    prev_node = lst.get_head()
    # To store values of nodes which we already visited
    visited_nodes = set()
    # If List is not empty and there is more than 1 element in List
    if not lst.is_empty() and current_node.next_element:
        while current_node:
            value = current_node.data
            if value in visited_nodes:
                # current_node is already in the HashSet
                # connect prev_node with current_node's next element
                # to remove it
                prev_node.next_element = current_node.next_element
                current_node = current_node.next_element
                continue
            # Visiting currentNode for first time
            visited_nodes.add(current_node.data)
            prev_node = current_node
            current_node = current_node.next_element

This uses the same concept that you have but instead of a list, it uses a hash table which improves the time complexity to O(n).

#3

That makes sense! Thanks a lot!