My short python solution with O(n) space complexity, could I do better?


  • 1
    E

    This solution makes a map between new members of the node class and existing members so the space complexity is O(n), although AFAIK, that's unavoidable since a deep copy must replicated the objects in the first palace. As best as I can tell, the solution is O(n) time.

    If anybody can elaborate on space complexity that would be really helpful, I know that I am probably not seeing something important here.

    def make_copy(node, tracker):
        # Base cases: None or existing nodes are returned w/o recursion
        if node is None:
            return None
        elif node in tracker:
            return tracker[node]
        # Make new node instance and map it to the old node
        newnode = RandomListNode(node.label)
        tracker[node] = newnode
        # recursively copy the next and random pointers before return
        newnode.next = make_copy(node.next, tracker)
        newnode.random = make_copy(node.random, tracker)
        return newnode
    
    
    class Solution:
        # @param head, a RandomListNode
        # @return a RandomListNode
        def copyRandomList(self, head):
            allnodes = {}
            newhead = make_copy(head, allnodes)
            return newhead

  • 0
    D

    your code are so short. It's easy to understand . below is my code. It's too much line code than you.
    but I think there is no need so much recursion call.

    class Solution:
        # @param head, a RandomListNode
        # @return a RandomListNode
        def __init__(self):
            self.nodeMap = {}
        def copyRandomList(self, head):
            nodeMap = self.nodeMap
            randomList = []
            if head == None:
                return None
                
            temp = head
            nHead = None
            nPrev = None
            while temp != None:
                node = RandomListNode(temp.label)
                if temp not in nodeMap:
                    nodeMap[temp] = node
                else:
                    break
                if temp.random != None:
                    if temp.random not in nodeMap:
                        randomList.append((node,temp))
                    else:
                        node.random = nodeMap[temp.random]
                
                if nHead == None:
                    nHead = node
                    nPrev = node
                else:
                    nPrev.next = node
                    nPrev = nPrev.next
                temp = temp.next
            while randomList != []:
                node, srcNode = randomList.pop()
                if srcNode.random not in nodeMap:
                    node.random = self.copyRandomList(srcNode.random)
                else:
                    node.random = nodeMap[srcNode.random]
            return nHead

  • 0
    I

    I made almost the same solution, but it failed to pass one very long input.
    So I just copy your code, it meets the same problem.

    class Solution:
        # @param head, a RandomListNode
        # @return a RandomListNode
        def __init__(self):
            self.all = {}
            
        def copyRandomList(self, head):
            if not head:
                return
            new = RandomListNode(head.label)
            self.all[head] = new
            
            if head.next in self.all:
                new.next = self.all[head.next]
            else:
                new.next = self.copyRandomList(head.next)
            
    
            if head.random in self.all:
                new.random = self.all[head.random]
            else:
                new.random = self.copyRandomList(head.random)
    
                
            return new

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.