Introduction

In this blog post, we will explore how to solve the LeetCode problem "1129" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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] = [ai, bi] indicates that there is a directed red edge from node ai to node bi in the graph, and blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj in the graph. 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 <= ai, bi, uj, vj < n

Explanation

Here's the solution:

• Build Adjacency Lists: Create separate adjacency lists for red and blue edges to represent the graph.
• Breadth-First Search (BFS): Perform a BFS starting from node 0, keeping track of the distance and the color of the last edge used in the path. Explore paths by alternating between red and blue edges.

• Track Visited Nodes: Use a 3D array to track visited nodes based on the node index and the color of the last edge used to reach that node (red or blue). This prevents cycles.

• Runtime Complexity: O(n + E), where n is the number of nodes and E is the total number of edges. Storage Complexity: O(n + E)

Code

    from collections import deque

def shortestAlternatingPaths(n: int, redEdges: list[list[int]], blueEdges: list[list[int]]) -> list[int]:
    red_adj = [[] for _ in range(n)]
    blue_adj = [[] for _ in range(n)]

    for u, v in redEdges:
        red_adj[u].append(v)
    for u, v in blueEdges:
        blue_adj[u].append(v)

    answer = [-1] * n
    answer[0] = 0

    q = deque([(0, 0, None)])  # (node, distance, last_color)  None means starting node

    visited = [[[False, False] for _ in range(n)] for _ in range(1)]  # Visited[node][0] is visited by red, Visited[node][1] is visited by blue
    visited[0][0] = [True, True] # mark node 0 as visited by both red and blue for the initial BFS

    while q:
        node, dist, last_color = q.popleft()

        if last_color != 'red':
            for neighbor in red_adj[node]:
                if not visited[0][neighbor][0]:
                    visited[0][neighbor][0] = True
                    if answer[neighbor] == -1:
                        answer[neighbor] = dist + 1
                    q.append((neighbor, dist + 1, 'red'))

        if last_color != 'blue':
            for neighbor in blue_adj[node]:
                if not visited[0][neighbor][1]:
                    visited[0][neighbor][1] = True
                    if answer[neighbor] == -1:
                        answer[neighbor] = dist + 1
                    q.append((neighbor, dist + 1, 'blue'))

    return answer