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 Search Breadth-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] = [u_i, v_i] represents a directed edge going from node u_i to node v_i.

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

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 <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= u_i == edges[i][0] < n
0 <= v_i == edges[i][1] < n
u_i != v_i
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:

Initialize a counter for reversals to zero.
Perform a graph traversal (like BFS or DFS) starting from i on the underlying undirected graph structure.
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.
During the traversal, whenever we move from a node u to a neighbor v, we check the original direction of the edge between them.
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.
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].
This process is repeated for all n nodes.

1import java.util.*;2 3class Solution {4    public int[] minEdgeReversals(int n, int[][] edges) {5        // Store original directed edges for quick lookup6        Set<String> originalEdges = new HashSet<>();7        List<List<Integer>> adj = new ArrayList<>();8        for (int i = 0; i < n; i++) {9            adj.add(new ArrayList<>());10        }11 12        for (int[] edge : edges) {13            int u = edge[0];14            int v = edge[1];15            originalEdges.add(u + "," + v);16            adj.get(u).add(v);17            adj.get(v).add(u);18        }19 20        int[] answer = new int[n];21        for (int i = 0; i < n; i++) {22            answer[i] = countReversalsForRoot(i, n, adj, originalEdges);23        }24        return answer;25    }26 27    private int countReversalsForRoot(int root, int n, List<List<Integer>> adj, Set<String> originalEdges) {28        int reversals = 0;29        Queue<Integer> queue = new LinkedList<>();30        boolean[] visited = new boolean[n];31 32        queue.offer(root);33        visited[root] = true;34 35        while (!queue.isEmpty()) {36            int u = queue.poll();37            for (int v : adj.get(u)) {38                if (!visited[v]) {39                    visited[v] = true;40                    // We are traversing from u to v.41                    // The edge should be u -> v.42                    // If the original edge is v -> u, we need a reversal.43                    if (originalEdges.contains(v + "," + u)) {44                        reversals++;45                    }46                    queue.offer(v);47                }48            }49        }50        return reversals;51    }52}

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

This approach avoids redundant calculations by using a dynamic programming technique on the tree, often called "rerooting". It consists of two main passes (DFS traversals). The first pass calculates the answer for an arbitrary root (e.g., node 0). The second pass uses this result to efficiently compute the answers for all other nodes in linear time.

Algorithm

Build an adjacency list for the graph. For each directed edge u -> v, add v to u's neighbors with a cost of 0, and add u to v's neighbors with a cost of 1 (indicating a reversal is needed to traverse v -> u).
Initialize an answer array of size n.
First Pass (DFS):
- Perform a DFS from an arbitrary root (e.g., node 0).
- This DFS (dfs1) calculates the total reversals needed if node 0 is the root.
- In dfs1(u, parent), for each child v of u, add the cost of the u -> v traversal to answer[0]. Then, recurse on the child.
Second Pass (DFS):
- Perform another DFS from the same root (node 0).
- This DFS (dfs2) calculates the answer for each node based on its parent's answer.
- In dfs2(u, parent), for each child v of u:
  - The answer for v is derived from the answer for u. When the root moves from u to v, the cost associated with the edge (u, v) flips.
  - If the original edge was u -> v, answer[v] = answer[u] + 1.
  - If the original edge was v -> u, answer[v] = answer[u] - 1.
  - Recursively call dfs2(v, u).
Return the answer array.

Walkthrough

The core idea is that the answers for adjacent nodes are closely related. If we know the number of reversals for a node u to be the root, we can calculate the answer for its neighbor v with a simple update.

First Pass (DFS from an arbitrary root):

We start by choosing an arbitrary root, say node 0.
We build an adjacency list that represents the undirected tree structure but also encodes the original edge directions. For each original edge u -> v, we can add (v, 0) to u's adjacency list and (u, 1) to v's list. The second element in the pair represents the cost of traversal: 0 for following the original direction and 1 for going against it (a reversal).
We perform a post-order DFS traversal (dfs1) starting from the root 0. This traversal calculates answer[0], the number of reversals needed to make 0 the universal source. During the traversal from a parent u to a child v, if the edge u -> v is against the original direction (cost is 1), we add 1 to our total count.

Second Pass (Rerooting DFS):

Now, we perform a second, pre-order DFS traversal (dfs2) starting from root 0 to calculate the answers for all other nodes.
When we move from a parent u to a child v, we can compute answer[v] based on answer[u].
When the root shifts from u to v, the required direction of the edge between them flips.
- If the original edge was u -> v, it was correctly oriented for root u (cost 0), but needs to be reversed for root v (cost 1). So, answer[v] will be one more than answer[u] would be, considering only this edge's change.
- If the original edge was v -> u, it was incorrectly oriented for root u (cost 1), but is now correctly oriented for root v (cost 0). So, answer[v] will be one less.
The formula is: answer[v] = answer[u] + (original edge u->v ? 1 : -1).
We apply this formula recursively down the tree.

1import java.util.*;2 3class Solution {4    List<List<int[]>> adj;5    int[] answer;6 7    public int[] minEdgeReversals(int n, int[][] edges) {8        adj = new ArrayList<>();9        for (int i = 0; i < n; i++) {10            adj.add(new ArrayList<>());11        }12 13        for (int[] edge : edges) {14            int u = edge[0];15            int v = edge[1];16            // u -> v: cost 0 from u to v, cost 1 from v to u17            adj.get(u).add(new int[]{v, 0});18            adj.get(v).add(new int[]{u, 1});19        }20 21        answer = new int[n];22        23        // First DFS to calculate answer for root 024        dfs1(0, -1);25        26        // Second DFS to calculate answers for all other nodes27        dfs2(0, -1);28        29        return answer;30    }31 32    // DFS to calculate the cost for the tree rooted at 0.33    private void dfs1(int u, int p) {34        for (int[] edgeInfo : adj.get(u)) {35            int v = edgeInfo[0];36            int cost = edgeInfo[1];37            if (v == p) continue;38            answer[0] += cost; // cost is 1 if edge is v->u, needs reversal for u->v39            dfs1(v, u);40        }41    }42 43    // DFS to compute answers for all nodes based on the parent's answer44    private void dfs2(int u, int p) {45        for (int[] edgeInfo : adj.get(u)) {46            int v = edgeInfo[0];47            int cost = edgeInfo[1];48            if (v == p) continue;49            50            // When moving root from u to v:51            // If original edge was u->v (cost=0), we need to reverse it. Cost increases by 1.52            // If original edge was v->u (cost=1), it's now in the correct direction. Cost decreases by 1.53            // The change is 1 - 2*cost. If cost=0, change=1. If cost=1, change=-1.54            answer[v] = answer[u] + (1 - 2 * cost);55            dfs2(v, u);56        }57    }58}

Complexity

Time

O(N). Building the adjacency list takes `O(N)` time. Both DFS traversals visit each node and edge once, taking `O(N + E)` time, which is `O(N)` as `E = N-1`.

Space

O(N). The adjacency list requires `O(N)` space. The recursion stack for DFS can go up to `O(N)` in the worst case (a linear tree). The `answer` array also takes `O(N)` space.

Trade-offs

Pros

Highly efficient with linear time complexity, making it suitable for large inputs.
Elegantly solves the problem by reusing previously computed results.

Cons

The logic, especially the rerooting step, can be less intuitive to grasp compared to the brute-force method.

Solutions

Solution

1class Solution {2private3  List<int[]>[] g;4private5  int[] ans;6public7  int[] minEdgeReversals(int n, int[][] edges) {8    ans = new int[n];9    g = new List[n];10    Arrays.setAll(g, i->new ArrayList<>());11    for (var e : edges) {12      int x = e[0], y = e[1];13      g[x].add(new int[]{y, 1});14      g[y].add(new int[]{x, -1});15    }16    dfs(0, -1);17    dfs2(0, -1);18    return ans;19  }20private21  void dfs(int i, int fa) {22    for (var ne : g[i]) {23      int j = ne[0], k = ne[1];24      if (j != fa) {25        ans[0] += k < 0 ? 1 : 0;26        dfs(j, i);27      }28    }29  }30private31  void dfs2(int i, int fa) {32    for (var ne : g[i]) {33      int j = ne[0], k = ne[1];34      if (j != fa) {35        ans[j] = ans[i] + k;36        dfs2(j, i);37      }38    }39  }40}

1class Solution {2public:3  vector<int> minEdgeReversals(int n, vector<vector<int>> &edges) {4    vector<pair<int, int>> g[n];5    vector<int> ans(n);6    for (auto &e : edges) {7      int x = e[0], y = e[1];8      g[x].emplace_back(y, 1);9      g[y].emplace_back(x, -1);10    }11    function<void(int, int)> dfs = [&](int i, int fa) {12      for (auto &[j, k] : g[i]) {13        if (j != fa) {14          ans[0] += k < 0;15          dfs(j, i);16        }17      }18    };19    function<void(int, int)> dfs2 = [&](int i, int fa) {20      for (auto &[j, k] : g[i]) {21        if (j != fa) {22          ans[j] = ans[i] + k;23          dfs2(j, i);24        }25      }26    };27    dfs(0, -1);28    dfs2(0, -1);29    return ans;30  }31};

1class Solution:2    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]: ans = [0] * n g = [[] for _ in range(n)] for x, y in edges: g[x]. append((y, 1)) g[y]. append((x, - 1)) def dfs(i: int, fa: int): for j, k in g[i]: if j != fa: ans[0] += int(k < 0) dfs(j, i) dfs(0, - 1) def dfs2(i: int, fa: int): for j, k in g[i]: if j != fa: ans[j] = ans[i] + k dfs2(j, i) dfs2(0, - 1) return ans

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 problem