Leetcode Problem 1129. Shortest Path with Alternating Colors

1129. Shortest Path with Alternating Colors

Leetcode Solutions

Breadth-First Search with Color Tracking

  1. Initialize an adjacency list adj to represent the graph, where adj[node] contains pairs (neighbor, color).
  2. Initialize an array answer with all elements set to -1, to store the shortest path lengths.
  3. Initialize a 2D array visit to track whether a node has been visited with a particular color.
  4. Initialize a queue to perform BFS, starting with node 0 with 0 steps and a placeholder color -1.
  5. While the queue is not empty, dequeue an element (node, steps, prevColor) and iterate over all (neighbor, color) pairs in adj[node].
  6. If neighbor has not been visited with color and color is not prevColor, enqueue (neighbor, steps + 1, color) and update answer[neighbor] if it's the first visit.
  7. Return the answer array.
UML Thumbnail

Two-Queue BFS for Red and Blue Edges

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...