How do you handle time limit exceeded errors in leetcode?-CodePudding

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]]

CodePudding user response：

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!

CodePudding user response：

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]