< Back





1129. Shortest Path with Alternating Colors

Fun question! We're given two sets of edges, red and blue, and asked for the shortest path from 0
to all the other nodes in the graph - if we can reach them. Otherwise, we return -1 for the length
of the shortest path to the unreachable nodes.

To easily solve this, we'll use BFS. We process the red edges and the blue edges, placing them in
separate graphs. We maintain a seen set that track the state of the node as well as the color of the
edge used to reach the node. We maintain a queue for each level that tracks the node, the distance
so far, and the color of the edge used to reach the node.

We process the nodes using BFS, maintaining the minimum distance to reach each node in our answer.
For each neighbor of the current node with the next color edge to traverse, we check to see if this
node has already been seen with the same color. If not, we add it to the seen list, and append it to
the queue, updating the color and distance.

At the end, we post process the answer to remove any float("inf") values and return the answer.

The solution is as follows:


  from collections import defaultdict

  class Solution:
      def shortestAlternatingPaths(
          self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]
      ) -> List[int]:
          red = 0
          blue = 1

          graph = defaultdict(lambda: defaultdict(list))

          for a, b in redEdges:
              graph[red][a].append(b)

          for u, v in blueEdges:
              graph[blue][u].append(v)

          ans = [float("inf")] * n
          queue = [(0, red, 0), (0, blue, 0)]
          seen = {(0, red), (0, blue)}

          while queue:
              curr_queue, queue = queue, []

              for node, color, distance in curr_queue:
                  ans[node] = min(ans[node], distance)

                  for neighbor in graph[color][node]:
                      if (neighbor, 1 - color) not in seen:
                          seen.add((neighbor, 1 - color))
                          queue.append((neighbor, 1 - color, distance + 1))

          return [distance if distance != float("inf") else -1 for distance in ans]


_ Time Complexity:

  O(n * m) - n is the number of nodes and m is the number of edges - standard BFS time complexity.

_ Space Complexity:

  O(n * m) - We process the nodes and edges and store them in an adjacency list.