How do you handle time limit exceeded errors in leetcode?

Question

Recently started solving leetcode problems and I tried to implement a linked list but I keep getting a time limit exceeded error. How can I solve this? The code runs perfectly well on sample input cases but I think it fails on edge cases. After going through various variations of code I haven't come up with a better way to implement a linked list. Here is my code

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
class MyLinkedList:

    def __init__(self):
        self.head =None

    def get(self, index: int) -> int:
        temp = self.head 
        
        if index == 0:
            return temp.data 
        pos = 0
        while temp is not None:
            if pos == index:
                return temp.data
                break
            # return temp.data
            temp = temp.next
            pos+=1
            
        if temp == None:
            return -1
            

    def addAtHead(self, val: int) -> None:
        new_node = Node(val)
        new_node.next = self.head
        self.head = new_node
        

    def addAtTail(self, val: int) -> None:
        new_node = Node(val)
        temp = self.head 
        if self.head is None:
            self.head = new_node
        while temp.next is not None:
            temp = temp.next
        temp.next =new_node
        

    def addAtIndex(self, index: int, val: int) -> None:
        new_node = Node(val)
        temp = self.head 
        if index ==0:
            new_node.next=temp
            self.head = new_node
        pos = 0
        while temp is not None:
            if pos == index:
                break
            prev = temp
            temp = temp.next
            pos+=1
            prev.next =new_node
            new_node.next=temp
        

    def deleteAtIndex(self, index: int) -> None:
        if self.head is None:
            return -1
        if index ==0:
            self.head = self.head.next
            return self.head
        pos =0
        curr = self.head
        prev=self.head 
        temp = self.head
        while curr is not None:
            if pos == index:
                temp = curr.next
                break
            prev = curr
            curr =curr.next
            pos+=1
        prev.next=temp
        return prev

And here is a sample input test case:

["MyLinkedList","addAtHead","addAtHead","addAtHead","addAtIndex","deleteAtIndex","addAtHead","addAtTail","get","addAtHead","addAtIndex","addAtHead"]
[[],[7],[2],[1],[3,0],[2],[6],[4],[4],[4],[5,0],[6]]

As a general answer: improve your solving algorithm (obviously) or remove sections of code that could be done more easily or are clogging up time. And: if edge cases can be solved more easily, take the east route. — Larry the Llama
– Larry the Llama, Commented Apr 3, 2022 at 9:39
Can you put here description of your problem, or link to LeetCode page with description? — Arty
– Arty, Commented Apr 3, 2022 at 9:39
@LarrytheLlama I cannot delete any of the functions inside the class as they are all evaluated by leetcode — narravabrion
– narravabrion, Commented Apr 3, 2022 at 10:34
@Arty here is a link to the problem leetcode.com/explore/learn/card/linked-list/209/… but I think you have to complete two lectures before you access the problem. — narravabrion
– narravabrion, Commented Apr 3, 2022 at 10:35
addAtIndex looks like it's wrong, because it sets prev.next and new_node.next on every iteration while it's finding the index. I haven't debugged further, but I guess somehow you end up with a circular linked list in some case and that's why you're getting timeouts. I suggest testing your code thoroughly with unit tests. — Paul Hankin
– Paul Hankin, Commented Apr 3, 2022 at 11:29

Muhammet Nusret Özateş · Accepted Answer · 2022-04-03 10:59:56Z

3

There are some optimizations you could do!

Have a reference for the tail. If you do that, you wouldn't have to traverse the list to addAtTail
Do you have to use a singly linked list? If not try using a doubly-linked list and always calculate the size of your list. Why this is useful?

let's say you have a linked list with 60 elements and you want to add at index 50. Wouldn't be better if you start from the tail and go back?

I will not add code examples because there are tons of resources on this topic. Good luck!

answered Apr 3, 2022 at 10:59

Muhammet Nusret Özateş

314 bronze badges

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

Comments

Arty · Accepted Answer · 2022-04-05 05:42:32Z

1

For reference adding link to problem, you have to login and skip first 3 introduction steps to see problem text. If you can't see text, here is an image of text.

Did 5-7 fixes to your code, main errors were in addAtIndex() and deleteAtIndex(), other functions contained small errors or typos. Some errors resulted in infinite loop, that's why there was Time Exceeded error on LeetCode server.

Corrected code snippet is below. Compare its text to your original text (for example with command line windiff original.py corrected.py under Windows) to see what are differences.

Also included in snippet several test cases that were failing with your original code.

Try it online!

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
class MyLinkedList:

    def __init__(self):
        self.head =None

    def get(self, index: int) -> int:
        temp = self.head
        if temp is None:
            return -1
        if index == 0:
            return temp.data 
        pos = 0
        while temp is not None:
            if pos == index:
                return temp.data
                break
            # return temp.data
            temp = temp.next
            pos+=1
            
        if temp == None:
            return -1
            
    def toList(self):
        r = []
        for i in range(1 << 30):
            v = self.get(i)
            if v == -1:
                return r
            r.append(v)
        
    def addAtHead(self, val: int) -> None:
        new_node = Node(val)
        new_node.next = self.head
        self.head = new_node
        

    def addAtTail(self, val: int) -> None:
        new_node = Node(val)
        temp = self.head 
        if self.head is None:
            self.head = new_node
            return
        while temp.next is not None:
            temp = temp.next
        temp.next =new_node
        

    def addAtIndex(self, index: int, val: int) -> None:
        new_node = Node(val)
        temp = self.head 
        if index ==0:
            new_node.next=temp
            self.head = new_node
            return
        pos = 0
        while True:
            if pos == index:
                prev.next = new_node
                new_node.next = temp
                break
            if temp is None:
                break
            prev = temp
            temp = temp.next
            pos+=1
        

    def deleteAtIndex(self, index: int) -> None:
        if self.head is None:
            return
        if index ==0:
            self.head = self.head.next
            return
        pos =0
        curr = self.head
        prev=self.head 
        temp = self.head
        while curr is not None:
            if pos == index:
                temp = curr.next
                prev.next=temp
                break
            prev = curr
            curr =curr.next
            pos+=1
        

def test():
    for itest, (meths, args) in enumerate([
        (["MyLinkedList","addAtHead","deleteAtIndex","addAtHead","addAtHead","addAtHead","addAtHead","addAtHead","addAtTail","get","deleteAtIndex","deleteAtIndex"],
         [[],[2],[1],[2],[7],[3],[2],[5],[5],[5],[6],[4]]),
        (["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get","get","deleteAtIndex","deleteAtIndex","get","deleteAtIndex","get"],
         [[],[1],[3],[1,2],[1],[1],[1],[3],[3],[0],[0],[0],[0]]),
        (["MyLinkedList","addAtIndex","get"],
         [[],[1,0],[0]]),
        (["MyLinkedList","addAtHead","addAtHead","addAtHead","addAtIndex","deleteAtIndex","addAtHead","addAtTail","get","addAtHead","addAtIndex","addAtHead"],
         [[],[7],[2],[1],[3,0],[2],[6],[4],[4],[4],[5,0],[6]]),
    ]):
        print('Test', itest)
        obj = None
        for meth, arg in zip(meths, args):
            print(meth, arg)
            if meth == 'MyLinkedList':
                obj = MyLinkedList(*arg)
            else:
                print('Result:', getattr(obj, meth)(*arg))
            print(obj.toList())

test()

Output:

Test 0
MyLinkedList []
[]
addAtHead [2]
Result: None
[2]
deleteAtIndex [1]
Result: None
[2]
addAtHead [2]
Result: None
[2, 2]
addAtHead [7]
Result: None
[7, 2, 2]
addAtHead [3]
Result: None
[3, 7, 2, 2]
addAtHead [2]
Result: None
[2, 3, 7, 2, 2]
addAtHead [5]
Result: None
[5, 2, 3, 7, 2, 2]
addAtTail [5]
Result: None
[5, 2, 3, 7, 2, 2, 5]
get [5]
Result: 2
[5, 2, 3, 7, 2, 2, 5]
deleteAtIndex [6]
Result: None
[5, 2, 3, 7, 2, 2]
deleteAtIndex [4]
Result: None
[5, 2, 3, 7, 2]
Test 1
MyLinkedList []
[]
addAtHead [1]
Result: None
[1]
addAtTail [3]
Result: None
[1, 3]
addAtIndex [1, 2]
Result: None
[1, 2, 3]
get [1]
Result: 2
[1, 2, 3]
deleteAtIndex [1]
Result: None
[1, 3]
get [1]
Result: 3
[1, 3]
get [3]
Result: -1
[1, 3]
deleteAtIndex [3]
Result: None
[1, 3]
deleteAtIndex [0]
Result: None
[3]
get [0]
Result: 3
[3]
deleteAtIndex [0]
Result: None
[]
get [0]
Result: -1
[]
Test 2
MyLinkedList []
[]
addAtIndex [1, 0]
Result: None
[]
get [0]
Result: -1
[]
Test 3
MyLinkedList []
[]
addAtHead [7]
Result: None
[7]
addAtHead [2]
Result: None
[2, 7]
addAtHead [1]
Result: None
[1, 2, 7]
addAtIndex [3, 0]
Result: None
[1, 2, 7, 0]
deleteAtIndex [2]
Result: None
[1, 2, 0]
addAtHead [6]
Result: None
[6, 1, 2, 0]
addAtTail [4]
Result: None
[6, 1, 2, 0, 4]
get [4]
Result: 4
[6, 1, 2, 0, 4]
addAtHead [4]
Result: None
[4, 6, 1, 2, 0, 4]
addAtIndex [5, 0]
Result: None
[4, 6, 1, 2, 0, 0, 4]
addAtHead [6]
Result: None
[6, 4, 6, 1, 2, 0, 0, 4]

answered Apr 5, 2022 at 5:42

Arty

17k6 gold badges60 silver badges96 bronze badges

8 Comments

narravabrion Over a year ago

Thank you for the insight. I've compared to my code and seen my errors. I'm only starting out with DSA so if you have any materials you can share I'd really appreciate. Thanks

Arty Over a year ago

@narravabrion If you think that my answer correctly answers your question, and/or what useful, don't forget to Accept and UpVote it. Accepting and UpVoting is done at the top of my answer's text, to the left handside from top - there is CheckMark sign, this checkmark Accepts answer, by accepting you just say that answer is correct, this will give me extra scores of reputation as a bonus for answering question. Also near checkmark there is Upper Array (triangle), this is UpVote button, probably it is not active now for you, because you have small reputation 11 score, UpVote marks helpful answer

Arty Over a year ago

@narravabrion Best educational material about Data Structures and Algorithms, to my mind is book Cormen - Algorithms, you can buy it (hardcover or kindle), or try to find it somewhere in internet in electronic format if it is available anywhere. Definitely don't buy it straight away before you read a dozen of pages, to figure out if you like it and if it is what you need information-wise.

narravabrion Over a year ago

Thank you for the material. Your answers was useful. Unfortunately I don't have enough reputation to upvote but I've accepted your answer.

Arty Over a year ago

@narravabrion Don't know if it was You that gave me 1 UpVote just today, but I see you have 58 reputation, which is enough for up-voting now. Just reminding, in case if you still wanted to up-vote it (if you didn't yet).

|

Collectives™ on Stack Overflow

How do you handle time limit exceeded errors in leetcode?

2 Answers 2

Comments

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related