FastPrep
Problem · Graph

Minimum Edge Reversals to Root a Tree

Learn this problem
● HardUber logoUberFULLTIMEOA
See Uber hiring insights

Problem statement

You are given a directed version of a tree with n nodes labeled from 0 to n - 1. Each undirected edge of the tree appears once in the input as a directed edge u -> v.

You may choose any node as the root. After choosing the root, every edge should point away from that root. You may reverse edges, and each reversed edge costs 1.

Return the minimum number of edge reversals needed over all possible root choices.

Function

minEdgeReversalsForRoot(n: int, edges: int[][]) → int

Complete the function minEdgeReversalsForRoot in the editor below.

minEdgeReversalsForRoot has the following parameters:

  1. int n: the number of nodes
  2. int[][] edges: directed edges where edges[i] = [u, v] means the current direction is u -> v

Returns

int: the minimum number of reversals required.

Examples

Example 1

n = 5edges = [[0, 1], [2, 1], [3, 2], [3, 4]]return = 1

If node 3 is chosen as the root, the desired directions are 3 -> 2 -> 1 -> 0 and 3 -> 4. Only the edge 0 -> 1 must be reversed.

Example 2

n = 4edges = [[2, 0], [0, 1], [2, 3]]return = 0

Choosing node 2 as the root already makes every edge point away from the root, so no reversals are needed.

Constraints

The source thread did not provide explicit numeric bounds.

  • The underlying undirected graph formed by edges is a tree.
  • edges.length = n - 1.
  • Each input edge gives the current direction of exactly one tree edge.

More Uber problems

drafts saved locally
public int minEdgeReversalsForRoot(int n, int[][] edges) {
    // write your code here
}
n5
edges[[0, 1], [2, 1], [3, 2], [3, 4]]
expected1
checking account