1129. Shortest Path with Alternating Colors

Medium

3.1K

164

You are given an integer `n`

, the number of nodes in a directed graph where the nodes are labeled from `0`

to `n - 1`

. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays `redEdges`

and `blueEdges`

where:

`redEdges[i] = [a`

indicates that there is a directed red edge from node_{i}, b_{i}]`a`

to node_{i}`b`

in the graph, and_{i}`blueEdges[j] = [u`

indicates that there is a directed blue edge from node_{j}, v_{j}]`u`

to node_{j}`v`

in the graph._{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 does not 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]

**Constraints:**

`1 <= n <= 100`

`0 <= redEdges.length, blueEdges.length <= 400`

`redEdges[i].length == blueEdges[j].length == 2`

`0 <= a`

_{i}, b_{i}, u_{j}, v_{j}< n

Accepted

94.8K

Submissions

195.5K

Acceptance Rate

48.5%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved