Practice/Microsoft/Leetcode 2858. Minimum Edge Reversals So Every Node Is Reachable

Leetcode 2858. Minimum Edge Reversals So Every Node Is Reachable

CodingOptional

Problem

You are given a tree represented as a directed graph with n nodes labeled from 0 to n-1. The graph has n-1 directed edges, and its underlying undirected structure forms a tree (connected, acyclic).

For each node in the tree, determine the minimum number of edge reversals needed so that starting from that node, you can reach every other node in the tree by following the directed edges.

An edge reversal means changing the direction of a directed edge. For example, if there's an edge from node u to node v, reversing it creates an edge from node v to node u.

Return an array answer of length n, where answer[i] is the minimum number of edge reversals required when starting from node i.

Requirements

1. Build an efficient representation of the tree that tracks both the original directed edges and allows bidirectional traversal
2. For each node, calculate the minimum reversals needed to make all other nodes reachable from it
3. Use tree rerooting or similar dynamic programming technique to avoid redundant computation
4. Return the results as an array indexed by node number

Constraints

• 2 <= n <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ui, vi < n
• ui != vi
• The underlying undirected graph is a tree (connected and acyclic)
• Time complexity should be O(n) for optimal solution
• Space complexity should be O(n)

Examples

Example 1:

` Input: n = 3, edges = [[0,1],[1,2]] Output: [1,0,1] Explanation:

• From node 0: The edge 0→1 is correct, but to reach node 2 we need to reverse edge 1→2, so 1 reversal total
• From node 1: We can reach node 2 directly (0→1 reversed becomes 1→0, and 1→2 stays), optimal is 0 reversals
• From node 2: Need to reverse 1→2 to get to 1, and then reverse 0→1 to get to 0, but optimal is 1 reversal `

Example 2:

` Input: n = 4, edges = [[0,1],[0,2],[0,3]] Output: [0,1,1,1] Explanation:

• From node 0: All edges point away from 0, so all nodes are already reachable with 0 reversals
• From node 1: Need to reverse 0→1 to reach 0 (1 reversal), then can reach 2 and 3 through 0
• Similar logic for nodes 2 and 3 `

Example 3:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] Output: [4,3,2,3,4] Explanation: This is a linear chain. From the middle node (2), we need 2 reversals total. As we move away from the center, the cost increases symmetrically.