Shortest Path with Alternating Colors

Problem

You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to node n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays redEdges and blueEdges where:

redEdges[i] = [ai, bi] indicates that there is a directed red edge from node ai to node bi in the graph, and
blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj in the graph.

Return an array answer of length n, where each answer[x] is the length of the shortest path from node 0 to node x such that the edge colors alternate along the path, or -1 if such a path does not exist.

Examples

Example 1:

1
2
3
4


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

Example 2:

1
2
3
4


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

Solution

Method 1 - BFS with Color State

Intuition

The shortest path with alternating colors can be found using BFS, but we must track the color of the last edge used to ensure alternation. By exploring both red and blue edges from each node, and keeping track of the color used to reach each node, we avoid revisiting the same state and ensure the shortest path is found.

Approach

Build two adjacency lists: one for red edges and one for blue edges.
Use a queue for BFS, where each state is (node, last_color). Start from node 0 with both colors.
Track visited states as (node, color) to avoid cycles.
For each node, try to traverse edges of the opposite color from the last edge used.
Record the shortest distance to each node for both colors, and at the end, take the minimum for each node.
If a node is unreachable, return -1 for that node.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<vector<int>> red(n), blue(n);
        for (auto& e : redEdges) red[e[0]].push_back(e[1]);
        for (auto& e : blueEdges) blue[e[0]].push_back(e[1]);
        vector<vector<int>> dist(n, vector<int>(2, 1e9));
        queue<pair<int, int>> q;
        dist[0][0] = dist[0][1] = 0;
        q.push({0, 0}); // 0: red, 1: blue
        q.push({0, 1});
        while (!q.empty()) {
            auto [u, c] = q.front(); q.pop();
            auto& next = c == 0 ? blue : red;
            for (int v : next[u]) {
                if (dist[v][1-c] == 1e9) {
                    dist[v][1-c] = dist[u][c] + 1;
                    q.push({v, 1-c});
                }
            }
        }
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            int d = min(dist[i][0], dist[i][1]);
            ans[i] = d == 1e9 ? -1 : d;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


type pair struct{u, c, d int}
func shortestAlternatingPaths(n int, redEdges [][]int, blueEdges [][]int) []int {
    red := make([][]int, n)
    blue := make([][]int, n)
    for _, e := range redEdges { red[e[0]] = append(red[e[0]], e[1]) }
    for _, e := range blueEdges { blue[e[0]] = append(blue[e[0]], e[1]) }
    dist := make([][2]int, n)
    for i := range dist { dist[i][0], dist[i][1] = 1e9, 1e9 }
    dist[0][0], dist[0][1] = 0, 0
    q := []pair{{0,0,0},{0,1,0}}
    for len(q) > 0 {
        p := q[0]; q = q[1:]
        next := red
        if p.c == 0 { next = blue }
        for _, v := range next[p.u] {
            if dist[v][1-p.c] == 1e9 {
                dist[v][1-p.c] = p.d + 1
                q = append(q, pair{v,1-p.c,p.d+1})
            }
        }
    }
    ans := make([]int, n)
    for i := range ans {
        d := dist[i][0]
        if dist[i][1] < d { d = dist[i][1] }
        if d == 1e9 { ans[i] = -1 } else { ans[i] = d }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<Integer>[] red = new List[n], blue = new List[n];
        for (int i = 0; i < n; ++i) red[i] = new ArrayList<>();
        for (int i = 0; i < n; ++i) blue[i] = new ArrayList<>();
        for (int[] e : redEdges) red[e[0]].add(e[1]);
        for (int[] e : blueEdges) blue[e[0]].add(e[1]);
        int[][] dist = new int[n][2];
        for (int[] d : dist) Arrays.fill(d, Integer.MAX_VALUE);
        dist[0][0] = dist[0][1] = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0,0});
        q.offer(new int[]{0,1});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int u = cur[0], c = cur[1];
            List<Integer>[] next = c == 0 ? blue : red;
            for (int v : next[u]) {
                if (dist[v][1-c] == Integer.MAX_VALUE) {
                    dist[v][1-c] = dist[u][c] + 1;
                    q.offer(new int[]{v,1-c});
                }
            }
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int d = Math.min(dist[i][0], dist[i][1]);
            ans[i] = d == Integer.MAX_VALUE ? -1 : d;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    fun shortestAlternatingPaths(n: Int, redEdges: Array<IntArray>, blueEdges: Array<IntArray>): IntArray {
        val red = Array(n) { mutableListOf<Int>() }
        val blue = Array(n) { mutableListOf<Int>() }
        for (e in redEdges) red[e[0]].add(e[1])
        for (e in blueEdges) blue[e[0]].add(e[1])
        val dist = Array(n) { IntArray(2) { Int.MAX_VALUE } }
        dist[0][0] = 0; dist[0][1] = 0
        val q = ArrayDeque<Pair<Int,Int>>()
        q.add(0 to 0); q.add(0 to 1)
        while (q.isNotEmpty()) {
            val (u, c) = q.removeFirst()
            val next = if (c == 0) blue else red
            for (v in next[u]) {
                if (dist[v][1-c] == Int.MAX_VALUE) {
                    dist[v][1-c] = dist[u][c] + 1
                    q.add(v to 1-c)
                }
            }
        }
        return IntArray(n) {
            val d = minOf(dist[it][0], dist[it][1])
            if (d == Int.MAX_VALUE) -1 else d
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: list[list[int]], blueEdges: list[list[int]]) -> list[int]:
        red = [[] for _ in range(n)]
        blue = [[] for _ in range(n)]
        for u, v in redEdges: red[u].append(v)
        for u, v in blueEdges: blue[u].append(v)
        dist = [[float('inf')] * 2 for _ in range(n)]
        dist[0][0] = dist[0][1] = 0
        from collections import deque
        q = deque([(0,0),(0,1)])
        while q:
            u, c = q.popleft()
            next_edges = blue if c == 0 else red
            for v in next_edges[u]:
                if dist[v][1-c] == float('inf'):
                    dist[v][1-c] = dist[u][c] + 1
                    q.append((v,1-c))
        ans = []
        for d0, d1 in dist:
            d = min(d0, d1)
            ans.append(-1 if d == float('inf') else d)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


impl Solution {
    pub fn shortest_alternating_paths(n: i32, red_edges: Vec<Vec<i32>>, blue_edges: Vec<Vec<i32>>) -> Vec<i32> {
        let n = n as usize;
        let mut red = vec![vec![]; n];
        let mut blue = vec![vec![]; n];
        for e in red_edges { red[e[0] as usize].push(e[1] as usize); }
        for e in blue_edges { blue[e[0] as usize].push(e[1] as usize); }
        let mut dist = vec![[i32::MAX; 2]; n];
        dist[0][0] = 0; dist[0][1] = 0;
        let mut q = std::collections::VecDeque::new();
        q.push_back((0,0)); q.push_back((0,1));
        while let Some((u, c)) = q.pop_front() {
            let next = if c == 0 { &blue } else { &red };
            for &v in &next[u] {
                if dist[v][1-c] == i32::MAX {
                    dist[v][1-c] = dist[u][c] + 1;
                    q.push_back((v,1-c));
                }
            }
        }
        dist.into_iter().map(|d| {
            let m = d[0].min(d[1]);
            if m == i32::MAX { -1 } else { m }
        }).collect()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    shortestAlternatingPaths(n: number, redEdges: number[][], blueEdges: number[][]): number[] {
        const red: number[][] = Array.from({length: n}, () => []);
        const blue: number[][] = Array.from({length: n}, () => []);
        for (const [u, v] of redEdges) red[u].push(v);
        for (const [u, v] of blueEdges) blue[u].push(v);
        const dist: number[][] = Array.from({length: n}, () => [Infinity, Infinity]);
        dist[0][0] = dist[0][1] = 0;
        const q: [number, number][] = [[0,0],[0,1]];
        while (q.length) {
            const [u, c] = q.shift()!;
            const next = c === 0 ? blue : red;
            for (const v of next[u]) {
                if (dist[v][1-c] === Infinity) {
                    dist[v][1-c] = dist[u][c] + 1;
                    q.push([v,1-c]);
                }
            }
        }
        return dist.map(([d0, d1]) => {
            const d = Math.min(d0, d1);
            return d === Infinity ? -1 : d;
        });
    }
}

Complexity

⏰ Time complexity: O(n + e), where n is the number of nodes and e is the total number of edges. Each edge is processed at most once for each color.
🧺 Space complexity: O(n + e), for adjacency lists and distance tracking for each node and color.

Problem#

Examples#

Solution#

Method 1 - BFS with Color State#

Intuition#

Approach#

Code#

Complexity#