 # Clone Graph Problem

### Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

## How To Nail Your Next Tech Interview Hosted By
Ryan Valles
Founder, Interview Kickstart Our tried & tested strategy for cracking interviews How FAANG hiring process works The 4 areas you must prepare for How you can accelerate your learnings

Given A Graph, Build A New One With Reversed Edges

Given a strongly connected directed graph, build a new graph with the same number of nodes but every edge reversed. This is also called transposing a graph.

Example

Input: Any node of this graph:

Output: Any node of the new:

Notes

Input Parameters: Function has one argument pointing to a node of the given graph.

Output: Return any node of the new graph.

Constraints:

● 1

● Value in any node will be a unique integer between 1 and number of nodes, inclusive.

● No multiple edges (connecting any pair of nodes in one direction) or self loops (edges connecting a node with itself) in the input graph.

● You are not allowed to modify the given graph. Return a newly built graph.

#### Solution

To solve this problem simple DFS will work. We provided one sample solution.

Time Complexity:

Our DFS-like algorithm takes O(n + m) time where n is the number of nodes and m is the number of edges.

Without multiple edges or self loops (which problem statement guarantees) the number of edges m can be as big as n*(n-1) in the worst case. So O(n^2) is the time complexity in terms of n.

Auxiliary Space Used:

O(n) for the call stack used by the recursive function dfs() in the worst case.

Space complexity:

Same O(n + m) or O(n^2) as in Time Complexity. Both input and output graphs take that much space.

``````
// -------- START --------

/*
In constraints we are given that each node contains distinct values, so we can keep track of
node address using that value. {value : node}
*/
static HashMap reversed_graph = new HashMap();

static void dfs(Node node)
{
// First create new node.
reversed_graph.put(node.val, new Node(node.val));
int n = node.neighbours.size();
// Visit all the neighbours.
for (int i = 0; i < n; i++)
{
// If node is not visited then first visit it.
if (reversed_graph.containsKey(node.neighbours.get(i).val) == false )
{
dfs(node.neighbours.get(i));
}
reversed_graph.get(node.val));
}
}

static Node build_other_graph(Node node)
{
// Build the graph.
dfs(node);
// Return any node of the new graph.
return reversed_graph.get(1);
}

// -------- END --------
``````

### Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

## How To Nail Your Next Tech Interview Hosted By
Ryan Valles
Founder, Interview Kickstart Our tried & tested strategy for cracking interviews How FAANG hiring process works The 4 areas you must prepare for How you can accelerate your learnings

All Posts