Scale Engineer

Minimum Edge Reversals So Every Node Is Reachable

Hard
#2555Time: O(N^2). For each of the `N` nodes, we perform a full graph traversal (BFS/DFS), which takes `O(N + E)` time. Since `E = N-1`, this is `O(N)`. Repeating this `N` times gives `O(N^2)`.Space: O(N). We need `O(N)` space for the adjacency list, `O(N)` for the `HashSet` of edges, and `O(N)` for the BFS queue and `visited` array.1 company
Patterns
Dynamic Programming
Algorithms
Depth-First SearchBreadth-First Search
Data structures
Graph
Companies
MathWorks

Prompt

There is a simple directed graph with n nodes labeled from 0 to n - 1. The graph would form a tree if its edges were bi-directional.

You are given an integer n and a 2D integer array edges, where edges[i] = [ui, vi] represents a directed edge going from node ui to node vi.

An edge reversal changes the direction of an edge, i.e., a directed edge going from node ui to node vi becomes a directed edge going from node vi to node ui.

For every node i in the range [0, n - 1], your task is to independently calculate the minimum number of edge reversals required so it is possible to reach any other node starting from node i through a sequence of directed edges.

Return an integer array answer, where answer[i] is the minimum number of edge reversals required so it is possible to reach any other node starting from node i through a sequence of directed edges.

 

Example 1:

Input: n = 4, edges = [[2,0],[2,1],[1,3]]
Output: [1,1,0,2]
Explanation: The image above shows the graph formed by the edges.
For node 0: after reversing the edge [2,0], it is possible to reach any other node starting from node 0.
So, answer[0] = 1.
For node 1: after reversing the edge [2,1], it is possible to reach any other node starting from node 1.
So, answer[1] = 1.
For node 2: it is already possible to reach any other node starting from node 2.
So, answer[2] = 0.
For node 3: after reversing the edges [1,3] and [2,1], it is possible to reach any other node starting from node 3.
So, answer[3] = 2.

Example 2:

Input: n = 3, edges = [[1,2],[2,0]]
Output: [2,0,1]
Explanation: The image above shows the graph formed by the edges.
For node 0: after reversing the edges [2,0] and [1,2], it is possible to reach any other node starting from node 0.
So, answer[0] = 2.
For node 1: it is already possible to reach any other node starting from node 1.
So, answer[1] = 0.
For node 2: after reversing the edge [1, 2], it is possible to reach any other node starting from node 2.
So, answer[2] = 1.

 

Constraints:

  • 2 <= n <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ui == edges[i][0] < n
  • 0 <= vi == edges[i][1] < n
  • ui != vi
  • The input is generated such that if the edges were bi-directional, the graph would be a tree.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each node from 0 to n-1, treating each one as a potential root. For each potential root, it calculates the minimum number of edge reversals required to make all other nodes reachable.

Algorithm

  • Create an adjacency list for the undirected version of the graph.
  • Store the original directed edges in a HashSet for efficient lookups.
  • Iterate through each node i from 0 to n-1.
    • For each i, perform a Breadth-First Search (BFS) or Depth-First Search (DFS) starting from i.
    • Initialize a reversals count to 0.
    • During the traversal from a node u to a neighbor v, check if the original edge was v -> u.
    • If it was, increment the reversals count.
    • After the traversal is complete, store the total reversals in answer[i].
  • Return the answer array.

Walkthrough

To make all nodes reachable from a starting node i, the graph must form a directed tree rooted at i, where all edges point away from the root. The underlying undirected graph is a tree, so there's a unique path from i to any other node j. We need to ensure all edges on these paths are directed away from i.

The algorithm for each potential root i is as follows:

  1. Initialize a counter for reversals to zero.
  2. Perform a graph traversal (like BFS or DFS) starting from i on the underlying undirected graph structure.
  3. To do this, we first build an undirected adjacency list from the given directed edges. We also need a way to check the original direction of an edge, for example, by storing the directed edges in a HashSet of pairs.
  4. During the traversal, whenever we move from a node u to a neighbor v, we check the original direction of the edge between them.
  5. If the original edge was v -> u, it's pointing towards the root i instead of away from it. This edge must be reversed, so we increment the reversal counter.
  6. After the traversal completes, the counter holds the total number of reversals needed for i to be the root. This value is stored in answer[i].
  7. This process is repeated for all n nodes.
import java.util.*; class Solution {    public int[] minEdgeReversals(int n, int[][] edges) {        // Store original directed edges for quick lookup        Set<String> originalEdges = new HashSet<>();        List<List<Integer>> adj = new ArrayList<>();        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }         for (int[] edge : edges) {            int u = edge[0];            int v = edge[1];            originalEdges.add(u + "," + v);            adj.get(u).add(v);            adj.get(v).add(u);        }         int[] answer = new int[n];        for (int i = 0; i < n; i++) {            answer[i] = countReversalsForRoot(i, n, adj, originalEdges);        }        return answer;    }     private int countReversalsForRoot(int root, int n, List<List<Integer>> adj, Set<String> originalEdges) {        int reversals = 0;        Queue<Integer> queue = new LinkedList<>();        boolean[] visited = new boolean[n];         queue.offer(root);        visited[root] = true;         while (!queue.isEmpty()) {            int u = queue.poll();            for (int v : adj.get(u)) {                if (!visited[v]) {                    visited[v] = true;                    // We are traversing from u to v.                    // The edge should be u -> v.                    // If the original edge is v -> u, we need a reversal.                    if (originalEdges.contains(v + "," + u)) {                        reversals++;                    }                    queue.offer(v);                }            }        }        return reversals;    }}

Complexity

Time

O(N^2). For each of the `N` nodes, we perform a full graph traversal (BFS/DFS), which takes `O(N + E)` time. Since `E = N-1`, this is `O(N)`. Repeating this `N` times gives `O(N^2)`.

Space

O(N). We need `O(N)` space for the adjacency list, `O(N)` for the `HashSet` of edges, and `O(N)` for the BFS queue and `visited` array.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly solves the problem by simulating the process for each node.

Cons

  • Inefficient due to re-computation. The O(N^2) time complexity is too slow for the given constraints (n <= 10^5).

Solutions

class Solution {private  List<int[]>[] g;private  int[] ans;public  int[] minEdgeReversals(int n, int[][] edges) {    ans = new int[n];    g = new List[n];    Arrays.setAll(g, i->new ArrayList<>());    for (var e : edges) {      int x = e[0], y = e[1];      g[x].add(new int[]{y, 1});      g[y].add(new int[]{x, -1});    }    dfs(0, -1);    dfs2(0, -1);    return ans;  }private  void dfs(int i, int fa) {    for (var ne : g[i]) {      int j = ne[0], k = ne[1];      if (j != fa) {        ans[0] += k < 0 ? 1 : 0;        dfs(j, i);      }    }  }private  void dfs2(int i, int fa) {    for (var ne : g[i]) {      int j = ne[0], k = ne[1];      if (j != fa) {        ans[j] = ans[i] + k;        dfs2(j, i);      }    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem