Accepted , but I Use O(n) space complexity


  • 1
    E

    I use O(n) time complexity and O(n)space complexity. is there some more efficient method? my method use an extra LinkedList<UndirectedGraphNode> as a queue and a HashMap<Integer, UndirectedGraphNode> to query quickly. so the run time is O(N). my Code is following:

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    	//use LinkedList to bread first search, only offer those first met nodes
    	LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
    	//use hashmap to query quickly
    	HashMap<Integer,UndirectedGraphNode> kv = new HashMap<Integer,UndirectedGraphNode>();
    	
    	if(node == null)
    		return null;
    	queue.offer(node);
    	while(!queue.isEmpty())
    	{
    		UndirectedGraphNode label = queue.poll();
    		if(kv.containsKey(label.label))
    		{
    			for(UndirectedGraphNode nei: label.neighbors)
    			{
    				if(kv.containsKey(nei.label))
    					kv.get(label.label).neighbors.add(kv.get(nei.label));
    				else
    				{
    					queue.offer(nei);
    					kv.put(nei.label, new UndirectedGraphNode(nei.label));
    					kv.get(label.label).neighbors.add(kv.get(nei.label));
    				}
    			}
    		}else
    		{
    			kv.put(label.label, new UndirectedGraphNode(label.label));
    			for(UndirectedGraphNode nei: label.neighbors)
    			{
    				if(kv.containsKey(nei.label))
    					kv.get(label.label).neighbors.add(kv.get(nei.label));
    				else
    				{
    					queue.offer(nei);
    					kv.put(nei.label, new UndirectedGraphNode(nei.label));
    					kv.get(label.label).neighbors.add(kv.get(nei.label));
    				}
    			}
    		}
    	}
    	return kv.get(node.label);
    }

  • 0
    1

    No, you have to clone n vertices, so you have to visit all the n vertices. This is obviously O(n).

    You also need to map the graph vertices to clone vertices. This requires n space. So it is optimal.


  • 4
    S

    Your code is accepted, but it's too long. Here is a simple ver:

    /**
     * O(n) time usage and O(n) space usage.
     * @param node of original graph
     * @return node of clone graph
     */
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    	if (node == null) 
    		return null;
    	
    	HashMap<Integer, UndirectedGraphNode> map = new HashMap<Integer, UndirectedGraphNode>();
    	LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
    	queue.offer(node);
    	UndirectedGraphNode curNode = null;
    	
    	//FIFO
    	while (!queue.isEmpty()) {
    		curNode = queue.poll();
    		if (!map.containsKey(curNode.label)) 
    			map.put(curNode.label, new UndirectedGraphNode(curNode.label));			
    		if (null != curNode.neighbors) {
    			for (UndirectedGraphNode neighbor : curNode.neighbors) {
    				if (!map.containsKey(neighbor.label)) {
    					queue.offer(neighbor);
    					map.put(neighbor.label, new UndirectedGraphNode(neighbor.label));		
    				}
    				map.get(curNode.label).neighbors.add(map.get(neighbor.label));
    			}
    		}
    	}  //end while
    	return map.get(node.label);
    }

  • 0
    Y

    I have similar one:

     public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if(node==null) return null;
            Queue<UndirectedGraphNode> qu=new LinkedList<>();
            Queue<UndirectedGraphNode> qu1=new LinkedList<>();
            HashMap<UndirectedGraphNode,UndirectedGraphNode> map=new HashMap<>();
            qu.add(node);
            UndirectedGraphNode res=new UndirectedGraphNode(node.label);
            qu1.add(res);
            map.put(node,res);
            while(!qu.isEmpty()){
                UndirectedGraphNode mynode=qu.remove();
                UndirectedGraphNode mynode1=qu1.remove();
                for(UndirectedGraphNode curNode:mynode.neighbors){
                    if(!map.keySet().contains(curNode)){
                        qu.add(curNode);
                        UndirectedGraphNode temp=new UndirectedGraphNode(curNode.label);
                        mynode1.neighbors.add(temp);
                        qu1.add(temp);
                        map.put(curNode,temp);
                    }
                    else{
                        mynode1.neighbors.add(map.get(curNode));
                    }
                }
            }
            return res;
        }

  • 0
    R

    Why would you need if (null != curNode.neighbors) check ? The constructor always initializes the neighbors ArrayList.


Log in to reply
 

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