Minimum edges to reverse to make path from source to destination

The problem, simply

You get a directed graph: V stops and E one-way streets. You want to drive from src to dst. You may flip the direction of any street, but you want to flip as few as possible.

Return the smallest number of flips that makes a route from src to dst possible, or -1 if even flipping everything cannot connect them.

A story to remember it

Picture it

Examples

Way 1: the simple way

Trying every set of streets to flip would mean 2^E tries. Instead, turn the problem into cheapest route: for every street u > v, add a road u to v with cost 0 and a road v to u with cost 1. The cheapest route from src to dst costs exactly the number of flips.

Find the cheapest route with Dijkstra: a min-heap always gives the closest unfinished stop.

import java.util.*;

class Solution {
    public int minFlips(int V, int[][] edges, int src, int dst) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], 0});   // right way: free
            adj.get(e[1]).add(new int[]{e[0], 1});   // wrong way: one flip
        }
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);   // {cost, stop}
        heap.add(new int[]{0, src});
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int d = top[0], u = top[1];
            if (d > dist[u]) continue;                  // an old entry
            for (int[] r : adj.get(u)) {
                if (d + r[1] < dist[r[0]]) {
                    dist[r[0]] = d + r[1];
                    heap.add(new int[]{dist[r[0]], r[0]});
                }
            }
        }
        return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
    }
}

How long it takes: Dijkstra with a heap, O(E log V). Extra room: the doubled road lists and the heap, O(V + E).

Way 2: the clever way

The costs are only 0 and 1, so a heap is more than we need. Use a two-ended line, a deque, and keep it sorted for free:

1. Build the doubled roads as in Way 1. Set dist[src] = 0 and put src in the line.
2. Take the stop u from the front.
3. For each road from u to v with cost w: if dist[u] + w < dist[v], update dist[v]. If w is 0, put v at the front (it is as close as u). If w is 1, put v at the back (one more than u).
4. When the line is empty, dist[dst] is the answer.

The line only ever holds stops with cost d at the front and d + 1 at the back, so the front is always a cheapest stop, exactly what Dijkstra's heap would give.

import java.util.*;

class Solution {
    public int minFlips(int V, int[][] edges, int src, int dst) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], 0});   // right way: free
            adj.get(e[1]).add(new int[]{e[0], 1});   // wrong way: one flip
        }
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        Deque<Integer> line = new ArrayDeque<>();
        line.addFirst(src);
        while (!line.isEmpty()) {
            int u = line.pollFirst();
            for (int[] r : adj.get(u)) {
                int v = r[0], w = r[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    if (w == 0) line.addFirst(v);      // free: as close as u
                    else line.addLast(v);              // one flip: wait at the back
                }
            }
        }
        return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
    }
}

How long it takes: each stop's cost can drop at most twice (from infinity to d + 1 to d), so every stop and road is handled a constant number of times, O(V + E). Extra room: the doubled road lists and the line, O(V + E).

Watch out for

• Forgetting the reverse road. Each street must add two roads: u to v for 0 and v to u for 1.
• Marking stops as done when you first push them, like plain BFS. A stop can get cheaper later (a free street can beat a flipped one), so compare costs instead.
• Returning dist[dst] while it is still Integer.MAX_VALUE. Return -1 then.
• Checking your answer by hand. In the example it is tempting to flip 2 to 1 and 5 to 1, but no route uses both; the route through 5 needs three flips (5 to 1, 4 to 5, 6 to 4). Walk the route to be sure.

What interviewers ask next

• Can you print which streets to flip? Store parent[v] = u and the cost of the road used when dist[v] improves, then walk back from dst.
• Minimum cost to make at least one valid path in a grid (LeetCode 1368)? Same trick: following a cell's arrow is free, any other direction costs 1, then 0-1 BFS on the grid.
• Reorient roads so every city can reach city 0 (LeetCode 1466)? Count the streets that point away from 0 during one search from 0. It is the same "right way 0, wrong way 1" idea on a tree.
• When is 0-1 BFS not enough? When costs can be other numbers. Then use Dijkstra, or a dial (bucket) queue when costs are small whole numbers.
• Why not plain BFS? Plain BFS counts streets, not flips. A long route of free streets beats a short route of flipped ones.

Remember this

Grown-up words: stops are vertices, one-way streets are directed edges, flipping is reversing an edge, the doubled roads make a 0-1 weighted graph, the two-ended line is a deque, and the method is 0-1 BFS, a faster Dijkstra for edge weights of 0 and 1.