# Accepted ， but I Use O(n) space complexity

• 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
//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))
else
{
queue.offer(nei);
kv.put(nei.label, new UndirectedGraphNode(nei.label));
}
}
}else
{
kv.put(label.label, new UndirectedGraphNode(label.label));
for(UndirectedGraphNode nei: label.neighbors)
{
if(kv.containsKey(nei.label))
else
{
queue.offer(nei);
kv.put(nei.label, new UndirectedGraphNode(nei.label));
}
}
}
}
return kv.get(node.label);
}``````

• 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.

• 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>();
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));
}
}
}
}  //end while
return map.get(node.label);
}``````

• I have similar one:

`````` public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node==null) return null;
HashMap<UndirectedGraphNode,UndirectedGraphNode> map=new HashMap<>();
UndirectedGraphNode res=new UndirectedGraphNode(node.label);
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)){
UndirectedGraphNode temp=new UndirectedGraphNode(curNode.label);
map.put(curNode,temp);
}
else{