Minimum Edge Reversals So Every Node Is Reachable solution and explanation
Google
9 more videos on this problem
🔴 2858. Minimum Edge Reversals So Every Node Is Reachable II Graph II DP II Leetcode 2858Aryan Mittal · 27:43 · 7K views
2858. Minimum Edge Reversals So Every Node Is Reachable | Leetcode Biweekly 113codingMohan · 32:00 · 2K views
2858. Minimum Edge Reversals So Every Node Is Reachable (Leetcode Hard)Programming Live with Larry · 29:04 · 865 views
LeetCode 2858 - Minimum Edge Reversals so Every Node is Reachable - BFS - PythonO(N!) Algos · 11:38 · 844 views
2858. Minimum Edge Reversals So Every Node Is Reachable || || Biweekly Contest 113 || LeetcodeAshish Kumar · 23:00 · 716 views
Minimum Edge Reversals So Every Node Is Reachable (LeetCode Hard) (Python)WYCode · 9:21 · 550 views
【每日一题】LeetCode 2858. Minimum Edge Reversals So Every Node Is ReachableHuifeng Guan · 15:06 · 441 views
2858. Minimum Edge Reversals So Every Node Is Reachable || LeetcodeDCC NITA · 14:12 · 425 views
Leetcode 2858. Minimum Edge Reversals So Every Node Is Reachable (dp on trees)LetsCode · 17:18 · 397 views
Biweekly Contest 113 || Minimum Edge Reversals So Every Node Is Reachable || Easy ExplanationManas Kumar Panda · 18:28 · 266 views
The problem
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 <= 105edges.length == n - 1edges[i].length == 20 <= ui == edges[i][0] < n0 <= vi == edges[i][1] < nui != vi- The input is generated such that if the edges were bi-directional, the graph would be a tree.
Approach overview
Problem Overview: You are given a directed tree with n nodes. For each node, determine the minimum number of edge reversals required so every other node becomes reachable starting from that node. The output is an array where index i represents the minimum reversals needed if node i is treated as the root.
Approach 1: Reverse BFS Traversal (O(n) time, O(n) space)
Model each edge in both directions inside an adjacency list. The original direction has cost 0 and the reversed direction has cost 1. Run a Breadth-First Search from node 0 to count how many edges must be reversed so every node becomes reachable from this root. Each traversal accumulates the reversal cost based on edge direction. This produces the baseline number of reversals for node 0. The insight is that moving along an edge aligned with the direction requires no change, while going against it implies a reversal.
Approach 2: BFS Re-rooting Propagation (O(n) time, O(n) space)
After computing the reversal count for root 0, propagate results to all nodes using another BFS. When moving the root from node u to neighbor v, adjust the answer depending on edge orientation. If the original edge is u → v, re-rooting requires one extra reversal. If it is v → u, one reversal is saved. This local adjustment allows computing results for all nodes without recomputing the whole traversal. The graph is processed once, making it linear time.
Approach 3: Using BFS to Determine Minimum Edge Reversals from Root (O(n) time, O(n) space)
This variation focuses on computing the base cost from a single root using weighted traversal logic. Each edge contributes either 0 or 1 depending on whether it must be reversed relative to traversal direction. The algorithm iterates through neighbors and accumulates reversal costs while marking visited nodes. This approach isolates the core counting step and is useful before applying a re-rooting optimization.
Approach 4: Dynamic Programming with Tree Re-rooting (O(n) time, O(n) space)
Use Depth-First Search combined with a re-rooting technique often used in dynamic programming on trees. The first DFS calculates how many reversals are needed when node 0 is the root. A second DFS propagates results to children by adjusting counts depending on edge orientation. Re-rooting avoids recomputation by reusing parent results and modifying them with constant-time updates. This technique generalizes well to many tree DP problems where answers depend on the chosen root.
Recommended for interviews: The tree re-rooting dynamic programming approach is the expected optimal solution. It runs in linear time and demonstrates strong understanding of graph traversal and root transition logic. Starting with the BFS counting step helps clarify the problem, but implementing the re-rooting propagation shows deeper algorithmic skill.
Approach 1: Using BFS to Determine Minimum Edge Reversals from Root
This approach involves initially assuming node 0 as the starting root and calculating the minimum edge reversals needed to reach from node 0 to every other node. We first build an adjacency list, taking into account both forward and reverse edges, with a reverse edge counted as an additional cost of one for BFS traversal. Finally, we propagate the costs using BFS.
from collections import deque, defaultdict
def bfs_min_reversals(n, edges):
adjacency_list = defaultdict(list)
for u, v in edges:
adjacency_list[u].append((v, 0)) # original direction
adjacency_list[v].append((u, 1)) # reverse direction
# Minimum reversals array initialized to infinity
min_reversals = [float('inf')] * n
min_reversals[0] = 0
queue = deque([0])
while queue:
node = queue.popleft()
for neighbor, cost in adjacency_list[node]:
if min_reversals[node] + cost < min_reversals[neighbor]:
min_reversals[neighbor] = min_reversals[node] + cost
queue.append(neighbor)
return min_reversals
n = 3
edges = [[1, 2], [2, 0]]
print(bfs_min_reversals(n, edges))This Python solution uses a Breadth-First Search (BFS) to determine the minimum number of reversals needed to make all nodes reachable from the root (node 0). It builds an adjacency list representing the bidirectional edges, using a tuple to distinguish between forward and reverse edges by assigning a cost of 1 to reverse edges.
The BFS explores neighbors and adds them to the queue only if replacing the current path yields fewer reversals than previously recorded via a dynamic programming approach, ensuring all possibilities are explored while maintaining optimal substructure.
Functionally, it calculates and returns the result for each node as the minimum reversals needed for reachability from that node.
Time Complexity: O(n), since each edge is processed only once in the BFS traversal.
Space Complexity: O(n), due to the storage requirement for the graph adjacency list and the min_reversals array.
Approach 2: Dynamic Programming with Tree Re-rooting
After calculating the minimum reversals needed from a fixed root (say node 0), we shift the root through each node. By analyzing the relationship between a node and its children, and leveraging already computed information from the original root, we can dynamically calculate the reversal cost for each node without recomputing from scratch.
def dfs(root, parent, adjacency, res):
for neighbor, cost in adjacency[root]:
if neighbor == parent:
continue
res[neighbor] = res[root] + cost
dfs(neighbor, root, adjacency, res)
def calculate_reversals(n, edges):
adjacency_list = defaultdict(list)
for u, v in edges:
adjacency_list[u].append((v, 0)) # forward edge
adjacency_list[v].append((u, 1)) # reverse edge
res = [0] * n # Starting assumption: node 0 is the root
dfs(0, -1, adjacency_list, res)
return res
n = 3
edges = [[1, 2], [2, 0]]
print(calculate_reversals(n, edges))In this Python implementation, we first assume node 0 as the root node and perform a DFS to visit each node from this root (node 0). During the DFS traversal, the minimum number of reversals from the root to each node is dynamically updated.
Through tree re-rooting, this implementation shifts the root node dynamically and recalculates the reversal counts. It leverages the costs already calculated on a parent node to efficiently compute the edge reversal cost for children nodes.
Time Complexity: O(n), as DFS explores each node and edge once for all structural transformations.
Space Complexity: O(n), the space required mainly for the adjacency list and result storage.
Approach 3: Approach 1: Reverse BFS Traversal
The idea is to perform a reverse BFS traversal starting from each node, simulating the reversal of edges and calculating the required number of reversals.
Initially, consider reversing all the edges. Use Reverse BFS from each node to see how many reversals can be reverted back to the original direction and compute the minimal reversals needed.
def minEdgeReversals(n, edges):
from collections import deque, defaultdict
# Transform each edge to reversed edge and add them to a deque
adjList = defaultdict(list)
for u, v in edges:
adjList[u].append((v, 0)) # original edge
adjList[v].append((u, 1)) # reversed edge
def bfs(start):
visited = [-1] * n
visited[start] = 0
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor, reverse_cost in adjList[node]:
if visited[neighbor] == -1 or visited[neighbor] > visited[node] + reverse_cost:
visited[neighbor] = visited[node] + reverse_cost
queue.append(neighbor)
return visited
return [bfs(i)[i] for i in range(n)]#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) {
vector<vector<pair<int, int>>> adjList(n);
for (auto& edge : edges) {
adjList[edge[0]].push_back({edge[1], 0});
adjList[edge[1]].push_back({edge[0], 1});
}
auto bfs = [&](int start) {
vector<int> visited(n, -1);
queue<int> q;
visited[start] = 0;
q.push(start);
while (!q.empty()) {
int node = q.front(); q.pop();
for (auto& [neighbor, reverse_cost] : adjList[node]) {
if (visited[neighbor] == -1 || visited[neighbor] > visited[node] + reverse_cost) {
visited[neighbor] = visited[node] + reverse_cost;
q.push(neighbor);
}
}
}
return visited;
};
vector<int> answer(n);
for (int i = 0; i < n; ++i) {
vector<int> distances = bfs(i);
answer[i] = distances[i];
}
return answer;
}We create an adjacency list where each edge appears as both directed and reversed. Using BFS, we traverse the graph starting from each node, updating the minimum reversal calculation based on edge directions. This provides the minimum number of reversals to reach all nodes from each starting node.
Time Complexity: O(n), where n is the number of nodes, as each edge is visited a constant number of times.
Space Complexity: O(n), required for the adjacency list and BFS queue.
Approach 4: Approach 2: Dynamic Programming with DFS
Utilize a dynamic programming strategy with DFS to compute the answer by adopting a similar logic to the tree-diameter problem where we calculate the cost to traverse back to the starting node after visiting each other node.
import java.util.*;
public class MinEdgeReversals {
static class Edge {
int neighbor, cost;
Edge(int n, int c) { neighbor = n; cost = c; }
}
public int[] minEdgeReversals(int n, int[][] edges) {
List<Edge>[] adjList = new ArrayList[n];
for (int i = 0; i < n; i++) adjList[i] = new ArrayList<>();
for (int[] edge : edges) {
adjList[edge[0]].add(new Edge(edge[1], 0));
adjList[edge[1]].add(new Edge(edge[0], 1));
}
int[] answer = new int[n];
class DFS {
int[] dfs(int node, int parent, int[] res) {
for (Edge e : adjList[node]) {
if (e.neighbor == parent) continue;
res[e.neighbor] = res[node] + e.cost;
dfs(e.neighbor, node, res);
}
return res;
}
}
for (int i = 0; i < n; i++) {
DFS dfs = new DFS();
int[] res = new int[n];
answer[i] = dfs.dfs(i, -1, res)[i];
}
return answer;
}
}function minEdgeReversals(n, edges) {
const adjList = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adjList[u].push([v, 0]);
adjList[v].push([u, 1]);
}
const answer = Array(n).fill(0);
function dfs(node, parent, res) {
for (const [neighbor, cost] of adjList[node]) {
if (neighbor === parent) continue;
res[neighbor] = res[node] + cost;
dfs(neighbor, node, res);
}
}
for (let i = 0; i < n; i++) {
const res = Array(n).fill(0);
dfs(i, -1, res);
answer[i] = res[i];
}
return answer;
}This solution exploits the properties of DFS in a tree structure, calculating the minimum edge reversals by dynamically computing costs through recursive traversal. This approach is similar to tree-diameter problems.
Time Complexity: O(n), as each node and edge is visited a constant number of times.
Space Complexity: O(n), used for the adjacency list and recursive call stack.
Approach 5: Default Approach
function minEdgeReversals(n: number, edges: number[][]): number[] {
const g: number[][][] = Array.from({ length: n }, () => []);
for (const [x, y] of edges) {
g[x].push([y, 1]);
g[y].push([x, -1]);
}
const ans: number[] = Array(n).fill(0);
const dfs = (i: number, fa: number) => {
for (const [j, k] of g[i]) {
if (j !== fa) {
ans[0] += k < 0 ? 1 : 0;
dfs(j, i);
}
}
};
const dfs2 = (i: number, fa: number) => {
for (const [j, k] of g[i]) {
if (j !== fa) {
ans[j] = ans[i] + k;
dfs2(j, i);
}
}
};
dfs(0, -1);
dfs2(0, -1);
return ans;
}func minEdgeReversals(n int, edges [][]int) []int {
g := make([][][2]int, n)
for _, e := range edges {
x, y := e[0], e[1]
g[x] = append(g[x], [2]int{y, 1})
g[y] = append(g[y], [2]int{x, -1})
}
ans := make([]int, n)
var dfs func(int, int)
var dfs2 func(int, int)
dfs = func(i, fa int) {
for _, ne := range g[i] {
j, k := ne[0], ne[1]
if j != fa {
if k < 0 {
ans[0]++
}
dfs(j, i)
}
}
}
dfs2 = func(i, fa int) {
for _, ne := range g[i] {
j, k := ne[0], ne[1]
if j != fa {
ans[j] = ans[i] + k
dfs2(j, i)
}
}
}
dfs(0, -1)
dfs2(0, -1)
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using BFS to Determine Minimum Edge Reversals from Root | Time Complexity: O(n), since each edge is processed only once in the BFS traversal. Space Complexity: O(n), due to the storage requirement for the graph adjacency list and the min_reversals array. |
| Dynamic Programming with Tree Re-rooting | Time Complexity: O(n), as DFS explores each node and edge once for all structural transformations. Space Complexity: O(n), the space required mainly for the adjacency list and result storage. |
| Approach 1: Reverse BFS Traversal | Time Complexity: O(n), where n is the number of nodes, as each edge is visited a constant number of times. |
| Approach 2: Dynamic Programming with DFS | Time Complexity: O(n), as each node and edge is visited a constant number of times. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse BFS Traversal | O(n) | O(n) | Compute base reversal count from a single root |
| BFS Re-rooting Propagation | O(n) | O(n) | Efficiently derive answers for all nodes after initial root computation |
| BFS Root Cost Calculation | O(n) | O(n) | Understanding the core reversal counting logic |
| Dynamic Programming with DFS (Tree Re-rooting) | O(n) | O(n) | Interview‑optimal solution for computing results for every node |
Frequently asked questions
Is Minimum Edge Reversals So Every Node Is Reachable easy or hard?
LeetCode classifies this problem as Hard because it requires recognizing the tree re-rooting technique. The implementation combines graph traversal with dynamic programming logic to update results when the root shifts. Once the re-rooting insight is clear, the code becomes manageable.
Minimum Edge Reversals So Every Node Is Reachable Python/Java solution
Python, Java, C++, and JavaScript implementations all follow the same idea: build a bidirectional adjacency list with reversal costs, compute the base answer from node 0, then propagate results using DFS or BFS re-rooting. The logic remains O(n) regardless of language.
How to solve Minimum Edge Reversals So Every Node Is Reachable in O(n)?
Build an adjacency list storing both directions of each edge and mark whether traversal requires a reversal. Run a DFS or BFS from node 0 to count the base reversals. Then perform a second traversal to propagate answers: moving the root across an edge adds or subtracts one reversal depending on its direction. Each node is visited once, giving O(n) complexity.
What is the best approach for Minimum Edge Reversals So Every Node Is Reachable?
Tree re-rooting with DFS or BFS propagation is the optimal approach. First compute the number of reversals required when node 0 is the root. Then propagate results to all other nodes by adjusting counts depending on edge direction. This avoids recomputing the entire traversal for each node and runs in O(n) time.
Is Minimum Edge Reversals So Every Node Is Reachable asked at Google/Amazon/Meta?
Graph traversal and tree re-rooting problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of BFS/DFS, edge orientation, and dynamic programming on trees. The re-rooting technique is a common interview pattern.
What data structure is used in Minimum Edge Reversals So Every Node Is Reachable?
The core data structure is an adjacency list representing the graph. Each edge is stored with a direction flag indicating whether reversing it costs 1. The algorithm then uses BFS or DFS traversal along with arrays to store reversal counts for each node.
What is the time complexity of Minimum Edge Reversals So Every Node Is Reachable?
The optimal solution runs in O(n) time and O(n) space where n is the number of nodes. Each edge is processed a constant number of times during the initial traversal and the re-rooting pass. Since the graph is a tree with n-1 edges, the algorithm remains linear.