Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1129.html

1129. Shortest Path with Alternating Colors

Level

Medium

Description

Consider a directed graph, with nodes labelled 0, 1, ..., n-1. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.

Each [i, j] in red_edges denotes a red directed edge from node i to node j. Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.

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 doesn’t exist).

Example 1:

Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []

Output: [0,1,-1]

Example 2:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]

Output: [0,1,-1]

Example 3:

Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]

Output: [0,-1,-1]

Example 4:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]

Output: [0,1,2]

Example 5:

Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]

Output: [0,1,1]

Constraints:

  • 1 <= n <= 100
  • red_edges.length <= 400
  • blue_edges.length <= 400
  • red_edges[i].length == blue_edges[i].length == 2
  • 0 <= red_edges[i][j], blue_edges[i][j] < n

Solution

The idea is to use breadth first search. However, since there are two kinds of edges that have different colors and it is required that the edge colors altenate along the path, how to represent the states should be considered carefully.

In traditional breadth first search, only one state needs to be maintained for each node. However, in this problem, for each node there are two possible starting paths and two possible current paths, so four states need to be maintained for each node.

Initialize all nodes to unvisited and all distances to Integer.MAX_VALUE. For each node, store its starting path and current path as well, so each element is represented as an array [nodeIndex, startPath, curPath]. The two initial elements that are offered to the queue are [0, RED, RED] and [0, BLUE, BLUE]. Each time an element is polled from the queue, obtain all possible next nodes using curPath, obtain nextPath that is different from curPath, and update the next nodes’ states that are reachable currently (that is, the state that uses startPath and nextPath).

After all the nodes are visited, for each node, obtain its minimum possible distance, and return the distances.

  • class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges) {
        Map<Integer, List<Integer>> redEdgesMap = new HashMap<Integer, List<Integer>>();
        for (int[] redEdge : red_edges) {
            int src = redEdge[0], dst = redEdge[1];
            List<Integer> dstList = redEdgesMap.getOrDefault(src, new ArrayList<Integer>());
            dstList.add(dst);
            redEdgesMap.put(src, dstList);
        }
        Map<Integer, List<Integer>> blueEdgesMap = new HashMap<Integer, List<Integer>>();
        for (int[] blueEdge : blue_edges) {
            int src = blueEdge[0], dst = blueEdge[1];
            List<Integer> dstList = blueEdgesMap.getOrDefault(src, new ArrayList<Integer>());
            dstList.add(dst);
            blueEdgesMap.put(src, dstList);
        }
        final int WHITE = 0;
        final int GRAY = 1;
        final int BLACK = 2;
        final int RED = 0;
        final int BLUE = 1;
        int[][] colors = new int[n][4];
        int[][] distances = new int[n][4];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 4; j++)
                distances[i][j] = Integer.MAX_VALUE;
        }
        colors[0][0] = GRAY;
        colors[0][3] = GRAY;
        distances[0][0] = 0;
        distances[0][3] = 0;
        Queue<int[]> queue = new LinkedList<int[]>();
        for (int i = 0; i < 2; i++)
            queue.offer(new int[]{0, i, i});
        while (!queue.isEmpty()) {
            int[] indexPath = queue.poll();
            int index = indexPath[0], startPath = indexPath[1], path = indexPath[2];
            int distance = distances[index][startPath * 2 + path];
            List<Integer> nextNodes = path == RED ? redEdgesMap.getOrDefault(index, new ArrayList<Integer>()) : blueEdgesMap.getOrDefault(index, new ArrayList<Integer>());
            int nextPath = RED + BLUE - path;
            for (int nextNode : nextNodes) {
                if (colors[nextNode][startPath * 2 + nextPath] == WHITE) {
                    colors[nextNode][startPath * 2 + nextPath] = GRAY;
                    distances[nextNode][startPath * 2 + nextPath] = distance + 1;
                    queue.offer(new int[]{nextNode, startPath, nextPath});
                }
            }
            colors[index][startPath * 2 + path] = BLACK;
        }
        int[] shortestDistances = new int[n];
        for (int i = 0; i < n; i++) {
            int shortestDistance = Integer.MAX_VALUE;
            for (int j = 0; j < 4; j++)
                shortestDistance = Math.min(shortestDistance, distances[i][j]);
            shortestDistances[i] = shortestDistance == Integer.MAX_VALUE ? -1 : shortestDistance;
        }
        return shortestDistances;
    }
}

  • // OJ: https://leetcode.com/problems/shortest-path-with-alternating-colors/
// Time: O(R + B + N^2)
// Space: O(N^2)
class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& R, vector<vector<int>>& B) {
        vector<int> a(n, -1), b(n, -1), ans(n, -1);
        a[0] = b[0] = ans[0] = 0;
        int G[100][100] = {};
        for (auto &r : R) G[r[0]][r[1]] = 1;
        for (auto &b : B) G[b[0]][b[1]] |= 2;
        queue<pair<int, int>> q;
        q.emplace(0, 3);
        int step = 1;
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto [u, color] = q.front();
                q.pop();
                for (int v = 0; v < n; ++v) {
                    if (a[v] == -1 && (G[u][v] & 1) && (color & 2)) {
                        q.emplace(v, 1);
                        a[v] = step;
                        ans[v] = ans[v] == -1 ? a[v] : min(a[v], ans[v]);
                    }
                    if (b[v] == -1 && (G[u][v] & 2) && (color & 1)) {
                        q.emplace(v, 2);
                        b[v] = step;
                        ans[v] = ans[v] == -1 ? b[v] : min(b[v], ans[v]);
                    }
                }
            }
            ++step;
        }
        return ans;
    }
};

  • class Solution:
    def shortestAlternatingPaths(
        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]
    ) -> List[int]:
        g = [defaultdict(list), defaultdict(list)]
        for i, j in redEdges:
            g[0][i].append(j)
        for i, j in blueEdges:
            g[1][i].append(j)
        ans = [-1] * n
        vis = set()
        q = deque([(0, 0), (0, 1)])
        d = 0
        while q:
            for _ in range(len(q)):
                i, c = q.popleft()
                if ans[i] == -1:
                    ans[i] = d
                vis.add((i, c))
                c ^= 1
                for j in g[c][i]:
                    if (j, c) not in vis:
                        q.append((j, c))
            d += 1
        return ans



  • func shortestAlternatingPaths(n int, redEdges [][]int, blueEdges [][]int) []int {
	g := [2][][]int{}
	for i := range g {
		g[i] = make([][]int, n)
	}
	for _, e := range redEdges {
		g[0][e[0]] = append(g[0][e[0]], e[1])
	}
	for _, e := range blueEdges {
		g[1][e[0]] = append(g[1][e[0]], e[1])
	}
	type pair struct{ i, c int }
	q := []pair{pair{0, 0}, pair{0, 1} }
	ans := make([]int, n)
	vis := make([][2]bool, n)
	for i := range ans {
		ans[i] = -1
	}
	d := 0
	for len(q) > 0 {
		for k := len(q); k > 0; k-- {
			p := q[0]
			q = q[1:]
			i, c := p.i, p.c
			if ans[i] == -1 {
				ans[i] = d
			}
			vis[i][c] = true
			c ^= 1
			for _, j := range g[c][i] {
				if !vis[j][c] {
					q = append(q, pair{j, c})
				}
			}
		}
		d++
	}
	return ans
}

All Problems

All Solutions