Could anyone help me solve the TimeOut problem?


  • 0
    J
    public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null) return null;
        Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        
        UndirectedGraphNode head = new UndirectedGraphNode(node.label);
        map.put(node, head);
        queue.offer(node);
        
        while(!queue.isEmpty()) {
            UndirectedGraphNode currNode = queue.poll();
            ArrayList<UndirectedGraphNode> list = currNode.neighbors;
            // If the node is not in the map, create a new copy node and store the pair in HashMap
            if(!map.containsKey(currNode)) {
                UndirectedGraphNode newNode = new UndirectedGraphNode(currNode.label);
                map.put(currNode, newNode);
            }
            for(int i = 0; i < list.size(); i ++) {
                UndirectedGraphNode neighborNode = list.get(i);
                queue.off(neighborNode);
                map.get(currNode).neighbors.add(neighborNode);
            }
        }
        return head;
    }
    

    }

    in the code above, I used Queue and HashMap. The Queue is used to traversal the graph, and map is used to store the node and copy node pairs.


  • 1
    M

    The error you are thinking of, where your algorithm takes too long to solve the problem, is "Time Limit Exceeded." TimeOut is a problem with the server, such as there being too much traffic at that time. Try submitting again.


  • 0
    G

    You should try to split this problem into two parts. In the first part you need to construct each node. In the second part you should construct all the links. May it be helpful !


  • 0
    S
    while(!queue.isEmpty()) {
        UndirectedGraphNode currNode = queue.poll();
        ArrayList<UndirectedGraphNode> list = currNode.neighbors;
        // If the node is not in the map, create a new copy node and store the pair in HashMap
        if(!map.containsKey(currNode)) {
            UndirectedGraphNode newNode = new UndirectedGraphNode(currNode.label);
            map.put(currNode, newNode);
        }
        for(int i = 0; i < list.size(); i ++) {
            UndirectedGraphNode neighborNode = list.get(i);
            queue.off(neighborNode);
            map.get(currNode).neighbors.add(neighborNode);
        }
    }
    

    The code above gives you the problem.

    First of all, the currNode must be in the map. Therefore there is no need to have a condition clause.

    second of all, when constructing new nodes, you should construct new node for every node in neighbor and make sure that you construct new nodes only for the nodes cannot be found in the Hashmap. Finally, push the nodes in neighbor(they have not shown in the hashmap) into the queue.


Log in to reply
 

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