How hard is LeetCode 1129. Shortest Path with Alternating Colors?

LeetCode 1129. Shortest Path with Alternating Colors is rated Medium on LeetCode.

What is the time complexity of LeetCode 1129. Shortest Path with Alternating Colors?

The Python solution on this page runs in O(n + m).

What is the space complexity of LeetCode 1129. Shortest Path with Alternating Colors?

The Python solution on this page uses O(n + m) auxiliary space.

What topics does LeetCode 1129. Shortest Path with Alternating Colors cover?

LeetCode 1129. Shortest Path with Alternating Colors is tagged Breadth-First Search and Graph on LeetCode.

Shortest Path with Alternating Colors — LeetCode 1129 Python Solution

MediumBreadth-First SearchGraph

Problem: #1129
Pattern: Breadth-First Search
Reading time: 4 min
Source: leetcode.com

The problem

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.

Example

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

Python solution

Python

class Solution:
    def shortestAlternatingPaths(
        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]
    ) -> List[int]:
        g = [defaultdict(list), defaultdict(list)]
        for i, j in redEdges:
            g[0][i].append(j)
        for i, j in blueEdges:
            g[1][i].append(j)
        ans = [-1] * n
        vis = set()
        q = deque([(0, 0), (0, 1)])
        d = 0
        while q:
            for _ in range(len(q)):
                i, c = q.popleft()
                if ans[i] == -1:
                    ans[i] = d
                vis.add((i, c))
                c ^= 1
                for j in g[c][i]:
                    if (j, c) not in vis:
                        q.append((j, c))
            d += 1
        return ans

Complexity

Measure	Complexity
Time	O(n + m)
Space	O(n + m) auxiliary

Pattern: Breadth-First Search

Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 1129. Shortest Path with Alternating Colors is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.

The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1129. Shortest Path with Alternating Colors?: LeetCode 1129. Shortest Path with Alternating Colors is rated Medium on LeetCode.
What is the time complexity of LeetCode 1129. Shortest Path with Alternating Colors?: The Python solution on this page runs in O(n + m).
What is the space complexity of LeetCode 1129. Shortest Path with Alternating Colors?: The Python solution on this page uses O(n + m) auxiliary space.
What topics does LeetCode 1129. Shortest Path with Alternating Colors cover?: LeetCode 1129. Shortest Path with Alternating Colors is tagged Breadth-First Search and Graph on LeetCode.