Reorder Routes to Make All Paths Lead to the City Zero

Med

#1354Time: O(N^2). The outer loop runs N-1 times. Inside the loop, the BFS to find a path takes O(N+M) = O(N) time since M=N-1. This results in a total time complexity of O(N*N).Space: O(N^2) in the worst case. The queue for BFS can store paths, and the total length of all paths can be quadratic in a star-like graph. The adjacency list and other sets take O(N) space.2 companies

Algorithms

Depth-First Search Breadth-First Search

Data structures

Graph

Companies

Docusign DRW

Prompt

There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [a_i, b_i] represents a road from city a_i to city b_i.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.

It's guaranteed that each city can reach city 0 after reorder.

Example 1:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 2:

Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Example 3:

Input: n = 3, connections = [[1,0],[2,0]]
Output: 0

Constraints:

2 <= n <= 5 * 10⁴
connections.length == n - 1
connections[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every city (from 1 to n-1). For each city, it finds the unique path to the capital (city 0) and checks the orientation of each edge along this path. If an edge is pointing away from the capital, it's counted as a required reorientation. A set is used to keep track of already reoriented edges to avoid double counting.

Algorithm

Build an undirected graph representation using an adjacency list.
Store the original directed roads in a Set for quick lookups.
Initialize a Set to store the unique edges that need to be flipped.
Loop through each city i from 1 to n-1.
Inside the loop, perform a Breadth-First Search (BFS) starting from city i to find the unique path to city 0.
During the BFS, keep track of the path taken to reach each node.
Once city 0 is reached, reconstruct the path from i to 0.
Iterate over the edges (u, v) in this path, where u is farther from 0 and v is closer.
For each edge, check if the original road was u -> v. If not (meaning it was v -> u), add it to the set of edges to flip.
Finally, the size of the set gives the minimum number of reorientations.

Walkthrough

The fundamental idea is to ensure that for every city, its path to the capital (city 0) consists of correctly oriented roads. We can tackle this by examining each city one by one.

For each city i (where i > 0), we find the single path that connects it to city 0 in the underlying tree structure. This can be done using a graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS). Once we have the path, say i -> p1 -> p2 -> ... -> 0, we check each segment. For a segment u -> v (where v is closer to 0), the road must be directed from u to v. If the original road was v -> u, it's pointing the wrong way and must be flipped.

To avoid counting the same flip multiple times (as edges are part of multiple paths), we use a Set to store the unique edges that require reorientation. The final answer is the size of this set.

This method is correct but highly inefficient because finding the path from each of the N-1 cities to the root takes approximately O(N) time, leading to an overall quadratic time complexity.

1import java.util.*;2 3class Solution {4    public int minReorder(int n, int[][] connections) {5        // Build undirected graph6        List<List<Integer>> adj = new ArrayList<>();7        for (int i = 0; i < n; i++) {8            adj.add(new ArrayList<>());9        }10        // Store original directions for O(1) lookup11        Set<String> roads = new HashSet<>();12        for (int[] conn : connections) {13            adj.get(conn[0]).add(conn[1]);14            adj.get(conn[1]).add(conn[0]);15            roads.add(conn[0] + "," + conn[1]);16        }17 18        Set<String> edgesToFlip = new HashSet<>();19 20        // For each city, find path to 0 and check edges21        for (int i = 1; i < n; i++) {22            // Find path from i to 0 using BFS23            Queue<List<Integer>> queue = new LinkedList<>();24            queue.add(Arrays.asList(i));25            boolean[] visited = new boolean[n];26            visited[i] = true;27 28            while (!queue.isEmpty()) {29                List<Integer> path = queue.poll();30                int u = path.get(path.size() - 1);31 32                if (u == 0) {33                    // Path found, check its edges34                    for (int k = 0; k < path.size() - 1; k++) {35                        int from = path.get(k);36                        int to = path.get(k + 1);37                        // Path needs edge from->to. If original is not from->to, it must be flipped.38                        if (!roads.contains(from + "," + to)) {39                            edgesToFlip.add(to + "," + from);40                        }41                    }42                    break; // Move to next city43                }44 45                for (int v : adj.get(u)) {46                    if (!visited[v]) {47                        visited[v] = true;48                        List<Integer> newPath = new ArrayList<>(path);49                        newPath.add(v);50                        queue.add(newPath);51                    }52                }53            }54        }55        return edgesToFlip.size();56    }57}

Complexity

Time

O(N^2). The outer loop runs N-1 times. Inside the loop, the BFS to find a path takes O(N+M) = O(N) time since M=N-1. This results in a total time complexity of O(N*N).

Space

O(N^2) in the worst case. The queue for BFS can store paths, and the total length of all paths can be quadratic in a star-like graph. The adjacency list and other sets take O(N) space.

Trade-offs

Pros

Conceptually straightforward, as it directly models the problem requirement for each city.

Cons

Extremely inefficient with a time complexity of O(N^2), which will lead to a 'Time Limit Exceeded' error on larger test cases.
The implementation is complex, requiring pathfinding and reconstruction for each node.
Performs a lot of redundant computations by repeatedly traversing the same edges for different starting cities.

This optimal approach involves a single traversal of the graph, starting from the capital (city 0). We can use either Depth-First Search (DFS) or Breadth-First Search (BFS). As we traverse away from the capital, we check the direction of each road. If a road is directed away from the capital (i.e., from an already visited node to a new node), it must be reoriented.

Algorithm

Reframe the problem: Instead of checking paths to city 0, we can start from city 0 and traverse outwards. Any road pointing away from city 0 must be reoriented.
Build an adjacency list that stores not only the neighbors but also the direction of the original road. For a connection u -> v, we can store (v, 1) in u's list and (u, 0) in v's list, where 1 indicates an original direction and 0 indicates an artificial/reverse edge for traversal.
Start a traversal (DFS or BFS) from city 0.
Maintain a count of reorientations, initialized to 0.
During the traversal, when moving from a visited node u to an unvisited node v:
- Check the direction of the edge between u and v.
- If the edge was originally u -> v (indicated by the direction flag 1), it means the road is pointing away from the capital. This road must be flipped, so we increment the count.
- If the edge was v -> u (direction flag 0), it's already pointing towards the capital, so no change is needed.
Continue the traversal until all cities are visited. The final count is the minimum number of reorientations.

Walkthrough

A more efficient way to solve this problem is to change our perspective. Instead of checking paths from all cities to city 0, we can start a single traversal from city 0 and explore the entire network. We can think of the graph as a tree rooted at city 0. For every city to be able to reach city 0, every edge in this tree must be directed towards the root (city 0).

We can use a Depth-First Search (DFS) or Breadth-First Search (BFS) for the traversal. Let's start at city 0. When we traverse from a node u to a neighbor v, u is closer to the root 0 than v. Therefore, the road between them must be oriented as v -> u.

If the original road was u -> v, it's pointing away from the capital and needs to be reoriented. We increment a counter for each such case. If the road was already v -> u, it's correctly oriented, and we do nothing.

To implement this, we build an adjacency list where for each original road u -> v, we add two entries: one for u pointing to v (marking it as an original-direction edge) and one for v pointing to u (marking it as a reverse-direction edge). During the traversal from the root, whenever we cross an original-direction edge, we count it as a necessary reorientation.

DFS Implementation

1import java.util.*;2 3class Solution {4    int reorientations = 0;5 6    public int minReorder(int n, int[][] connections) {7        List<List<int[]>> adj = new ArrayList<>();8        for (int i = 0; i < n; i++) {9            adj.add(new ArrayList<>());10        }11 12        for (int[] conn : connections) {13            // conn[0] -> conn[1]14            // Add edge from conn[0] to conn[1], direction 1 (original)15            adj.get(conn[0]).add(new int[]{conn[1], 1});16            // Add edge from conn[1] to conn[0], direction 0 (artificial for traversal)17            adj.get(conn[1]).add(new int[]{conn[0], 0});18        }19 20        dfs(0, -1, adj);21        return reorientations;22    }23 24    private void dfs(int u, int parent, List<List<int[]>> adj) {25        for (int[] edge : adj.get(u)) {26            int v = edge[0];27            int direction = edge[1];28 29            if (v == parent) {30                continue;31            }32 33            // If direction is 1, it's an edge u -> v.34            // Since we traverse from 0 outwards, u is closer to 0 than v.35            // This edge points away from the capital and needs to be flipped.36            if (direction == 1) {37                reorientations++;38            }39            40            dfs(v, u, adj);41        }42    }43}

BFS Implementation

1import java.util.*;2 3class Solution {4    public int minReorder(int n, int[][] connections) {5        List<List<int[]>> adj = new ArrayList<>();6        for (int i = 0; i < n; i++) {7            adj.add(new ArrayList<>());8        }9 10        for (int[] conn : connections) {11            adj.get(conn[0]).add(new int[]{conn[1], 1}); // 1 means original direction12            adj.get(conn[1]).add(new int[]{conn[0], 0}); // 0 means reverse direction13        }14 15        int reorientations = 0;16        Queue<Integer> queue = new LinkedList<>();17        queue.offer(0);18        boolean[] visited = new boolean[n];19        visited[0] = true;20 21        while (!queue.isEmpty()) {22            int u = queue.poll();23            for (int[] edge : adj.get(u)) {24                int v = edge[0];25                if (visited[v]) {26                    continue;27                }28                visited[v] = true;29                // If we traverse u -> v and the original edge was u -> v (direction=1),30                // it needs to be flipped.31                if (edge[1] == 1) {32                    reorientations++;33                }34                queue.offer(v);35            }36        }37        return reorientations;38    }39}

Complexity

Time

O(N). Both DFS and BFS visit each node and edge exactly once. Since the graph is a tree, it has N nodes and N-1 edges. The complexity is O(N + M) = O(N).

Space

O(N). The adjacency list requires O(N + M) = O(N) space as M=N-1. The recursion stack for DFS or the queue for BFS can also take up to O(N) space in the worst case (for a skewed tree).

Trade-offs

Pros

Optimal time and space complexity.
Solves the problem in a single pass over the graph.
The logic is clean and avoids redundant calculations.

Cons

Requires a slightly more complex graph representation to store edge directions along with connectivity.

Solutions

Solution

1class Solution {2private3  List<int[]>[] g;4public5  int minReorder(int n, int[][] connections) {6    g = new List[n];7    Arrays.setAll(g, k->new ArrayList<>());8    for (var e : connections) {9      int a = e[0], b = e[1];10      g[a].add(new int[]{b, 1});11      g[b].add(new int[]{a, 0});12    }13    return dfs(0, -1);14  }15private16  int dfs(int a, int fa) {17    int ans = 0;18    for (var e : g[a]) {19      int b = e[0], c = e[1];20      if (b != fa) {21        ans += c + dfs(b, a);22      }23    }24    return ans;25  }26}

1class Solution {2public:3  int minReorder(int n, vector<vector<int>> &connections) {4    vector<pair<int, int>> g[n];5    for (auto &e : connections) {6      int a = e[0], b = e[1];7      g[a].emplace_back(b, 1);8      g[b].emplace_back(a, 0);9    }10    function<int(int, int)> dfs = [&](int a, int fa) {11      int ans = 0;12      for (auto &[b, c] : g[a]) {13        if (b != fa) {14          ans += c + dfs(b, a);15        }16      }17      return ans;18    };19    return dfs(0, -1);20  }21};

1class Solution:2    def minReorder(self, n: int, connections: List[List[int]]) -> int: def dfs(a: int, fa: int) -> int: return sum(c + dfs(b, a) for b, c in g[a] if b != fa) g = [[] for _ in range(n)] for a, b in connections: g[a]. append((b, 1)) g[b]. append((a, 0)) return dfs(0, - 1)

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