Time limit exceed error when using a list but works when using set for Leetcode problem in python

Question

I am solving a leetcode problem to find the intersection point in a linkedlist. When I use the list it gives me time limit exceed error but when I use set it gives me the answer. As each node in LinkedList is different both set and list would have the same element

Below is my code

def getIntersectionNode(self, headA: ListNode, headB: ListNode):
        nodes = set()
        while headA != None:
            nodes.add(headA)
            headA = headA.next

        while headB != None:
            if headB in nodes:
                return headB
            headB = headB.next
        return None

What is the reason for error to occur when using list instead of set.

joostblack · Accepted Answer · 2021-04-20 08:03:12Z

1

In python sets are faster for checking if they contain a certain element. The following will be faster if nodes is a set.

if headB in nodes:

But for example iterating over a set would be slower than iterating over a list.

answered Apr 20, 2021 at 8:03

joostblack

2,5457 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

augurar · Accepted Answer · 2021-04-20 09:19:41Z

0

The in operator is implemented differently for a set and a list.

For a list, the code must iterate over the entire list to check each element, potentially a linear-time operation.
For a set, the code checks if a given element is present using its hash code in constant time (on average).

Suppose A has m nodes and B has n nodes, and the lists don't intersect (worst-case scenario). If nodes is a list, the algorithm will have to iterate over all the nodes of A for each node in B, giving a time complexity of Θ(m×n). By contrast, when using a set the time complexity will be Θ(m+n). For large values of m and n, this makes a big difference in the runtime of the function.

Here are some references on how hash tables (the basis for Python's set and dict data structures) work:

edited Apr 20, 2021 at 9:19

answered Apr 20, 2021 at 8:02

augurar

13.3k7 gold badges60 silver badges70 bronze badges

4 Comments

augurar Over a year ago

@AjinkyaGadgil You're welcome! If this answered your question you can click the "check mark" next to the answer to mark the question as solved.

Ajinkya Gadgil Over a year ago

I have one question though. How exactly the set checks in a larger list?

augurar Over a year ago

That's a complicated question to answer, I'll add a reference in my answer so you can read about how hash tables work.

Ajinkya Gadgil Over a year ago

Thanks. I will check the links.

Collectives™ on Stack Overflow

Time limit exceed error when using a list but works when using set for Leetcode problem in python

2 Answers 2

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related