Shortest Path with Alternating Colors

Medium
937.

Shortest Path with Alternating Colors

Shortest Path with Alternating Colors is a medium coding problem on breadth-first search and graph, asked in Amazon, Google, Microsoft and Sprinklr interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} redEdges
 * @param {number[][]} blueEdges
 * @return {number[]}
 */
var shortestAlternatingPaths = function(n, redEdges, blueEdges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Shortest Path with Alternating Colors — Problem & Solution

Shortest Path with Alternating Colors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Shortest Path with Alternating Colors is a medium coding problem on breadth-first search and graph, asked in Amazon, Google, Microsoft and Sprinklr interviews.

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

Hints for Shortest Path with Alternating Colors

  1. Hint 1

    A node's distance alone is not enough state — the colour you arrived by decides what you may use next.

  2. Hint 2

    So search over (node, lastColour) pairs, doubling the state space.

  3. Hint 3

    Node 0 starts in both states, since the first edge may be either colour.

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

  1. Build two adjacency lists, one per colour.
  2. Seed the queue with (0, red) and (0, blue), both at distance 0.
  3. From (u, c) follow edges of colour 1 - c to unvisited states.
  4. 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

Java

public static int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
    List<List<List<Integer>>> adj = new ArrayList<>();
    for (int c = 0; c < 2; c++) {
        List<List<Integer>> side = new ArrayList<>();
        for (int i = 0; i < n; i++) side.add(new ArrayList<>());
        adj.add(side);
    }
    for (int[] e : redEdges) adj.get(0).get(e[0]).add(e[1]);
    for (int[] e : blueEdges) adj.get(1).get(e[0]).add(e[1]);
    int[][] dist = new int[2][n];
    for (int c = 0; c < 2; c++) Arrays.fill(dist[c], -1);
    dist[0][0] = 0;
    dist[1][0] = 0;
    Deque<int[]> q = new ArrayDeque<>();
    q.add(new int[] { 0, 0 });
    q.add(new int[] { 0, 1 });
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int u = cur[0], c = cur[1], nc = 1 - c;
        for (int v : adj.get(nc).get(u)) {
            if (dist[nc][v] >= 0) continue;
            dist[nc][v] = dist[c][u] + 1;
            q.add(new int[] { v, nc });
        }
    }
    int[] out = new int[n];
    for (int i = 0; i < n; i++) {
        int a = dist[0][i], b = dist[1][i];
        if (a < 0) out[i] = b;
        else if (b < 0) out[i] = a;
        else out[i] = Math.min(a, b);
    }
    return out;
}

C++

vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
    vector<vector<vector<int>>> adj(2, vector<vector<int>>(n));
    for (auto& e : redEdges) adj[0][e[0]].push_back(e[1]);
    for (auto& e : blueEdges) adj[1][e[0]].push_back(e[1]);
    vector<vector<int>> dist(2, vector<int>(n, -1));
    dist[0][0] = 0;
    dist[1][0] = 0;
    vector<pair<int,int>> q = { { 0, 0 }, { 0, 1 } };
    for (size_t head = 0; head < q.size(); head++) {
        int u = q[head].first, c = q[head].second, nc = 1 - c;
        for (int v : adj[nc][u]) {
            if (dist[nc][v] >= 0) continue;
            dist[nc][v] = dist[c][u] + 1;
            q.push_back({ v, nc });
        }
    }
    vector<int> out(n);
    for (int i = 0; i < n; i++) {
        int a = dist[0][i], b = dist[1][i];
        if (a < 0) out[i] = b;
        else if (b < 0) out[i] = a;
        else out[i] = 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 156 breadth-first search problems · the whole catalogue

Learn the technique: Breadth-First Search (BFS) · Graph Data Structure