Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Shortest Path with Alternating Colors
Table of Contents

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time complexity

Space Complexity

Problem Statement

You have a directed graph with n nodes labeled from 0 to n-1. The graph has two types of edges: red and blue. You are given two arrays redEdges and blueEdges:

  • redEdges[i] = [ai, bi] means there's a red edge from node ai to node bi.
  • blueEdges[j] = [uj, vj] means there's a blue edge from node uj to node vj.

Find the shortest path from node 0 to each node x such that the edges alternate in colors. If there is no such path, return -1 for that node.

Return an array answer of length n, where answer[x] is the length of the shortest alternating path from node 0 to node x.

Examples

Example 1:

  • Input: n = 4, redEdges = [[0, 1], [1, 2], [2, 3]], blueEdges = [[0, 2], [2, 1], [1, 3]]
  • Expected Output: [0, 1, 1, 2]
Image
  • Justification:
    • Node 0 is the start, so distance is 0.
    • Shortest path to node 1 is directly from 0 using red edge.
    • Shortest path to node 2 is directly from 0 using blue edge.
    • Shortest path to node 3 is via node 1 using red then blue edge.

Example 2:

  • Input: n = 3, redEdges = [[0, 1]], blueEdges = [[2, 1]]
  • Expected Output: [0, 1, -1]
Image
  • Justification:
    • Node 0 is the start, so distance is 0.
    • Shortest path to node 1 is directly from 0 using red edge.
    • Node 2 is not reachable from node 0 with alternating colors.

Example 3:

  • Input: n = 5, redEdges = [[0, 1], [1, 3]], blueEdges = [[1, 2], [3, 4]]
  • Expected Output: [0, 1, 2, -1, -1]
Image
  • Justification:
    • Node 0 is the start, so distance is 0.
    • Shortest path to node 1 is directly from 0 using red edge.
    • Shortest path to node 2 is via node 1 using red then blue edge.
    • Shortest path to node 3 is via node 1 using red edge, but not with alternative colors.
    • Shortest path to node 4 is via node 3 using red then blue edge, but not with alternative colors.

Constraints:

  • 1 <= n <= 100
  • 0 <= redEdges.length, blueEdges.length <= 400
  • redEdges[i].length == blueEdges[j].length == 2
  • 0 <= ai, bi, uj, vj < n

Solution

To solve this problem, we can use a Breadth-First Search (BFS) approach because it helps find the shortest path in an unweighted graph. BFS explores all possible paths layer by layer, ensuring the shortest path is found. Here, we need to keep track of the colors of the edges to ensure the paths alternate colors. We can use a queue to explore each node, alternating the colors as we go. By maintaining a visited status for each node with both red and blue colors, we ensure we do not revisit nodes in an invalid manner, preventing cycles and redundant paths.

This approach ensures that we check all possible paths from the starting node, considering color alternations. It's efficient since BFS operates in O(V + E) time complexity, where V is the number of vertices and E is the number of edges. Given the graph's constraints, this is an optimal solution.

Step-by-Step Algorithm

  1. Initialize Data Structures:

    • Create two adjacency lists for the graph: one for red edges and one for blue edges.
    • Initialize a 2D result array res with size [2][n], filled with Integer.MAX_VALUE, to store the shortest path lengths. Set the starting node 0 distance to 0 for both colors (i.e., res[0][0] = 0 and res[1][0] = 0).

  2. Build Graph:

    • For each red edge [ai, bi] in redEdges, add bi to the adjacency list of ai in the red graph.
    • For each blue edge [uj, vj] in blueEdges, add vj to the adjacency list of uj in the blue graph.

  3. Initialize BFS Queue:

    • Create a queue to store the nodes along with the color of the last edge used to reach them. Initialize the queue with the starting node 0 for both red and blue edges (i.e., queue.add({0, 0}) and queue.add({0, 1})).

  4. Perform BFS:

    • While the queue is not empty:
      • Dequeue the first element from the queue, which gives the current node and the color of the last edge used to reach it.
      • For each neighbor of the current node in the graph of the opposite color:
        • If the neighbor has not been visited via the current path (i.e., res[1 - color][neighbor] == Integer.MAX_VALUE), update the shortest path length to this neighbor and add it to the queue.

  5. Generate Answer:

    • For each node, the shortest path is the minimum value between the paths found via red and blue edges.
    • If no valid path exists, set the distance to -1.

Algorithm Walkthrough

Example Input

  • n = 4
  • redEdges = [[0, 1], [1, 2], [2, 3]]
  • blueEdges = [[0, 2], [2, 1], [1, 3]]
Image

  1. Initialize Data Structures:

    • graph[0] (red edges): [[], [], [], []]
    • graph[1] (blue edges): [[], [], [], []]
    • res: [[0, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE], [0, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE]]
    • queue: [{0, 0}, {0, 1}] (node, color)

  2. Build Graph:

    • For red edges:
      • graph[0][0].add(1) -> graph[0]: [[1], [], [], []]
      • graph[0][1].add(2) -> graph[0]: [[1], [2], [], []]
      • graph[0][2].add(3) -> graph[0]: [[1], [2], [3], []]
    • For blue edges:
      • graph[1][0].add(2) -> graph[1]: [[2], [], [], []]
      • graph[1][2].add(1) -> graph[1]: [[2], [], [1], []]
      • graph[1][1].add(3) -> graph[1]: [[2], [3], [1], []]

  3. Initialize BFS Queue:

    • Queue starts as [{0, 0}, {0, 1}].

  4. Perform BFS:

    • Dequeue {0, 0} (node 0 with red edge):
      • Check blue neighbors of 0:
        • graph[1][0]: [2]
        • res[1][2] is Integer.MAX_VALUE:
          • Update res[1][2] = res[0][0] + 1 = 1
          • Enqueue {2, 1}
    • Dequeue {0, 1} (node 0 with blue edge):
      • Check red neighbors of 0:
        • graph[0][0]: [1]
        • res[0][1] is Integer.MAX_VALUE:
          • Update res[0][1] = res[1][0] + 1 = 1
          • Enqueue {1, 0}
    • Dequeue {2, 1} (node 2 with blue edge):
      • Check red neighbors of 2:
        • graph[0][2]: [3]
        • res[0][3] is Integer.MAX_VALUE:
          • Update res[0][3] = res[1][2] + 1 = 2
          • Enqueue {3, 0}
    • Dequeue {1, 0} (node 1 with red edge):
      • Check blue neighbors of 1:
        • graph[1][1]: [3]
        • res[1][3] is Integer.MAX_VALUE:
          • Update res[1][3] = res[0][1] + 1 = 2
          • Enqueue {3, 1}
    • Dequeue {3, 0} (node 3 with red edge):
      • No unvisited blue neighbors.
    • Dequeue {3, 1} (node 3 with blue edge):
      • No unvisited red neighbors.

  5. Generate Answer:

    • For each node i, the length of the shortest path is the minimum of res[0][i] and res[1][i]:
      • answer[0] = min(res[0][0], res[1][0]) = 0
      • answer[1] = min(res[0][1], res[1][1]) = 1
      • answer[2] = min(res[0][2], res[1][2]) = 1
      • answer[3] = min(res[0][3], res[1][3]) = 2
    • If no valid path exists, set the distance to -1.

Code

Python3
Python3
. . . .

Complexity Analysis

Time complexity

The time complexity of the algorithm is O(V + E), where (V) is the number of vertices (nodes) and (E) is the number of edges. This is because the BFS traversal explores each vertex and edge once.

Space Complexity

The space complexity is also O(V + E), due to the space needed for the graph representation and the BFS queue.

Mark as Completed

Table of Contents

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time complexity

Space Complexity