1129. Shortest Path with Alternating Colors

Shortest Path with Alternating Colors (LeetCode 1129) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Shortest Path (Bellman-Ford / BFS+K) subpattern.

How to solve Shortest Path with Alternating Colors

Shortest Path with Alternating Colors is a Bellman-Ford and BFS with K Stops problem, part of Graph Traversal Patterns (DFS & BFS). Find shortest paths with constraints using Bellman-Ford algorithm and BFS with limited stops.

Work towards the solution in these steps:

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.

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

The Shortest Path with Alternating Colors solution and editorial walks through the full approach with reference code.

Problem statement

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 rededges denotes a red directed edge from node i to node j. Similarly, each [i, j] in blueedges 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, rededges = [[0,1],[1,2]], blueedges = [] Output: [0,1,-1]

Example 2: Input: n = 3, rededges = [[0,1]], blueedges = [[2,1]] Output: [0,1,-1]

Example 3: Input: n = 3, rededges = [[1,0]], blueedges = [[2,1]] Output: [0,-1,-1]

Example 4: Input: n = 3, rededges = [[0,1]], blueedges = [[1,2]] Output: [0,1,2]

Example 5: Input: n = 3, rededges = [[0,1],[0,2]], blueedges = [[1,0]] Output: [0,1,1]

Constraints: 1 <= n <= 100 rededges.length <= 400 blueedges.length <= 400 rededges[i].length == blueedges[i].length == 2 0 <= rededges[i][j], blueedges[i][j] < n

Topics and companies

Topics: Breadth-first Search, Graph.

Reported in interviews at Amazon.

How to practise Shortest Path with Alternating Colors on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n + e) time and O(n + e) space.

Open Shortest Path with Alternating Colors in the code editor, or read the Shortest Path with Alternating Colors editorial for a worked solution with its approach and complexity analysis.

Where Shortest Path with Alternating Colors sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Shortest Path (Bellman-Ford / BFS+K) subpattern
• The full DSA patterns sheet

Problems related to Shortest Path with Alternating Colors

Other problems that use the same Shortest Path (Bellman-Ford / BFS+K) and Graph Traversal Patterns (DFS & BFS) techniques:

• Cheapest Flights Within K Stops — Medium, same subpattern
• Accounts Merge — Medium, same pattern
• Alien Dictionary — Hard, same pattern
• All Paths from Source Lead to Destination — Medium, same pattern
• Build a Matrix With Conditions — Hard, same pattern
• Bus Routes — Hard, same pattern

Shortest Path with Alternating Colors FAQ