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

0% completed

Vote For New Content
Shortest Path with Alternating Colors (medium)
Table of Contents

Problem Statement

Examples

Try it yourself

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

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
Mark as Completed

Table of Contents

Problem Statement

Examples

Try it yourself