1129. Shortest Path with Alternating Colors LeetCode Solution
In this guide, you will get 1129. Shortest Path with Alternating Colors LeetCode Solution with the best time and space complexity. The solution to Shortest Path with Alternating Colors problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Shortest Path with Alternating Colors
You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to 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.
1129. Shortest Path with Alternating Colors LeetCode Solution in C++
enum class Color { kInit, kRed, kBlue };
class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges,
vector<vector<int>>& blueEdges) {
vector<int> ans(n, -1);
vector<vector<pair<int, Color>>> graph(n); // graph[u] := [(v, edgeColor)]
queue<pair<int, Color>> q{{{0, Color::kInit}}}; // [(u, prevColor)]
for (const vector<int>& edge : redEdges) {
const int u = edge[0];
const int v = edge[1];
graph[u].emplace_back(v, Color::kRed);
}
for (const vector<int>& edge : blueEdges) {
const int u = edge[0];
const int v = edge[1];
graph[u].emplace_back(v, Color::kBlue);
}
for (int step = 0; !q.empty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
const auto [u, prevColor] = q.front();
q.pop();
ans[u] = ans[u] == -1 ? step : ans[u];
for (auto& [v, edgeColor] : graph[u]) {
if (v == -1 || edgeColor == prevColor)
continue;
q.emplace(v, edgeColor);
v = -1; // Mark (u, v) as used.
}
}
return ans;
}
}; /* code provided by PROGIEZ */
1129. Shortest Path with Alternating Colors LeetCode Solution in Java
enum Color { kInit, kRed, kBlue }
class Solution {
public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
int[] ans = new int[n];
Arrays.fill(ans, -1);
// graph[u] := [(v, edgeColor)]
List<Pair<Integer, Color>>[] graph = new List[n];
// [(u, prevColor)]
Queue<Pair<Integer, Color>> q = new ArrayDeque<>(List.of(new Pair<>(0, Color.kInit)));
for (int i = 0; i < n; ++i)
graph[i] = new ArrayList<>();
for (int[] edge : redEdges) {
final int u = edge[0];
final int v = edge[1];
graph[u].add(new Pair<>(v, Color.kRed));
}
for (int[] edge : blueEdges) {
final int u = edge[0];
final int v = edge[1];
graph[u].add(new Pair<>(v, Color.kBlue));
}
for (int step = 0; !q.isEmpty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
final int u = q.peek().getKey();
Color prevColor = q.poll().getValue();
ans[u] = ans[u] == -1 ? step : ans[u];
for (int i = 0; i < graph[u].size(); ++i) {
Pair<Integer, Color> node = graph[u].get(i);
final int v = node.getKey();
Color edgeColor = node.getValue();
if (v == -1 || edgeColor == prevColor)
continue;
q.add(new Pair<>(v, edgeColor));
// Mark (u, v) as used.
graph[u].set(i, new Pair<>(-1, edgeColor));
}
}
return ans;
}
} // code provided by PROGIEZ
1129. Shortest Path with Alternating Colors LeetCode Solution in Python
from enum import Enum
class Color(Enum):
kInit = 0
kRed = 1
kBlue = 2
class Solution:
def shortestAlternatingPaths(
self,
n: int,
redEdges: list[list[int]],
blueEdges: list[list[int]],
) -> list[int]:
ans = [-1] * n
graph = [[] for _ in range(n)] # graph[u] := [(v, edgeColor)]
q = collections.deque([(0, Color.kInit)]) # [(u, prevColor)]
for u, v in redEdges:
graph[u].append((v, Color.kRed))
for u, v in blueEdges:
graph[u].append((v, Color.kBlue))
step = 0
while q:
for _ in range(len(q)):
u, prevColor = q.popleft()
if ans[u] == -1:
ans[u] = step
for i, (v, edgeColor) in enumerate(graph[u]):
if v == -1 or edgeColor == prevColor:
continue
q.append((v, edgeColor))
graph[u][i] = (-1, edgeColor) # Mark (u, v) as used.
step += 1
return ans # code by PROGIEZ
