Shortest Path with Alternating Colors — Medium Problem & Solution

A directed graph on n nodes has red edges and blue edges, each given as a list of [from, to] pairs.

Difficulty: Medium
Topics: Breadth-First Search, Graph
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A directed graph on n nodes has red edges and blue edges, each given as a list of [from, to] pairs. Edges may repeat, and a red and a blue edge may join the same pair.

Return an array where entry i is the length of the shortest path from node 0 to node i whose edge colours alternate, or -1 if no such path exists.

Example 1

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]
Explanation: Reaching node 2 would need two reds in a row.

Example 2

Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]

Example 3

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

Constraints

1 <= n <= 100
0 <= redEdges.length, blueEdges.length <= 400
redEdges[i].length == blueEdges[j].length == 2
0 <= redEdges[i][0], redEdges[i][1], blueEdges[j][0], blueEdges[j][1] < n

How to solve Shortest Path with Alternating Colors

Breadth-first search over (node, colour-just-used) states. From a state the only legal moves use the other colour, so the alternation is built into the transition instead of being checked afterwards.

Approach

Build two adjacency lists, one per colour.
Seed the queue with (0, red) and (0, blue), both at distance 0.
From (u, c) follow edges of colour 1 - c to unvisited states.
Each node's answer is the smaller of its two state distances, or -1 if neither was reached.

Why it works

Carrying the colour in the state is what keeps BFS correct here: on the plain node graph the first arrival at a node may leave it in the wrong colour to continue, so plain BFS can report a distance that cannot actually be extended. With the colour in the state each is explored independently, and BFS's layer order still gives shortest distances.

Complexity

Time — O(n + m)
Space — O(n + m)

Pitfalls

Visiting by node instead of by (node, colour) throws away the state that matters.
Node 0 answers 0 regardless of colours.
Duplicate and parallel edges are allowed and change nothing.

Reference solution

Python

from typing import List
from collections import deque

def shortestAlternatingPaths(n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
    adj = [[[] for _ in range(n)], [[] for _ in range(n)]]
    for u, v in redEdges:
        adj[0][u].append(v)
    for u, v in blueEdges:
        adj[1][u].append(v)
    dist = [[-1] * n, [-1] * n]
    dist[0][0] = 0
    dist[1][0] = 0
    q = deque([(0, 0), (0, 1)])
    while q:
        u, c = q.popleft()
        nc = 1 - c
        for v in adj[nc][u]:
            if dist[nc][v] >= 0:
                continue
            dist[nc][v] = dist[c][u] + 1
            q.append((v, nc))
    out = []
    for i in range(n):
        a, b = dist[0][i], dist[1][i]
        if a < 0:
            out.append(b)
        elif b < 0:
            out.append(a)
        else:
            out.append(min(a, b))
    return out

JavaScript

var shortestAlternatingPaths = function(n, redEdges, blueEdges) {
    var i;
    var adj = [[], []];
    for (i = 0; i < n; i++) { adj[0].push([]); adj[1].push([]); }
    for (i = 0; i < redEdges.length; i++) adj[0][redEdges[i][0]].push(redEdges[i][1]);
    for (i = 0; i < blueEdges.length; i++) adj[1][blueEdges[i][0]].push(blueEdges[i][1]);
    var dist = [[], []];
    for (i = 0; i < n; i++) { dist[0].push(-1); dist[1].push(-1); }
    dist[0][0] = 0;
    dist[1][0] = 0;
    var q = [0, 1];
    var head = 0;
    while (head < q.length) {
        var key = q[head++];
        var u = key >> 1, c = key & 1;
        var nc = 1 - c;
        for (i = 0; i < adj[nc][u].length; i++) {
            var v = adj[nc][u][i];
            if (dist[nc][v] >= 0) continue;
            dist[nc][v] = dist[c][u] + 1;
            q.push((v << 1) | nc);
        }
    }
    var out = [];
    for (i = 0; i < n; i++) {
        var a = dist[0][i], b = dist[1][i];
        if (a < 0) out.push(b);
        else if (b < 0) out.push(a);
        else out.push(a < b ? a : b);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 65 breadth-first search problems · the whole catalogue