1129. Shortest Path with Alternating Colors

How to solve Shortest Path with Alternating Colors (LeetCode 1129): the approach in brief

The problem

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.

Pattern

Shortest Path with Alternating Colors is a Graph Traversal Patterns (DFS & BFS) problem, in the Shortest Path (Bellman-Ford / BFS+K) subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Find shortest paths with constraints using Bellman-Ford algorithm and BFS with limited stops.

Approach outline

1. Think about using a graph traversal technique like BFS to find the shortest paths since the problem asks for shortest distances in a graph.
2. Model the graph with adjacency lists separately for red and blue edges to easily access neighbors by edge color.
3. Since the path must alternate colors, consider keeping track of both the current node and the color of the edge used to reach it during BFS.

Complexity

The reference solution runs in O(n + e) time and O(n + e) space.

Asked at

Shortest Path with Alternating Colors has been reported in interviews at Amazon.