Shortest Path with Alternating Colors - Practice Coding Problems

Shortest Path with Alternating Colors - 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.

You are given two arrays redEdges and blueEdges where:

redEdges[i] = [a_i, b_i] indicates that there is a directed red edge from node a_i to node b_i in the graph
blueEdges[j] = [u_j, v_j] indicates that there is a directed blue edge from node u_j to node v_j 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.

Input & Output

Example 1 — Basic Alternating Path

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

› Output: [0,1,-1]

💡 Note: From node 0: reach node 1 via red edge (distance 1), cannot reach node 2 (would need blue edge after red, but no blue edges exist)

Example 2 — Multiple Alternating Paths

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

› Output: [0,1,2]

💡 Note: From node 0: reach node 1 via red edge (distance 1), reach node 2 via red then blue edge (distance 2, colors alternate properly)

Example 3 — Complex Graph with Multiple Options

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

› Output: [0,1,2]

💡 Note: From node 0: direct red edges to nodes 1 and 2 (both distance 1). The blue edge from 1 to 0 doesn't help reach new nodes.

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

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Directed graph with red and blue edges

Alternating Constraint

Path colors must alternate: red→blue→red or blue→red→blue

Output Array

Shortest distance from node 0 to each node, or -1 if impossible

Key Takeaway

🎯 Key Insight: Use BFS with state (node, last_color) to track alternating constraint while finding shortest paths

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use BFS with state tracking where each state represents (node, last_edge_color) to ensure alternating colors. Best approach is BFS with State Tracking for guaranteed shortest paths. Time: O(V+E), Space: O(V)

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Backtracking	O(2^(E+V))	O(V)	Try all possible paths from node 0 using DFS with color alternation
BFS with State Tracking	O(V + E)	O(V)	Use BFS to find shortest alternating paths by tracking node and last edge color

DFS with Backtracking — Algorithm Steps

For each target node, start DFS from node 0
At each step, only follow edges with opposite color from previous edge
Track minimum path length to each node

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin from node 0, try both red and blue edges

Alternate Colors

At each step, only use opposite color from previous edge

Track Minimum

Keep track of shortest valid path to each node

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_N 100

int redGraph[MAX_N][MAX_N], blueGraph[MAX_N][MAX_N];
int redCount[MAX_N], blueCount[MAX_N];
int visited[MAX_N][2]; // [node][color] where color: 0=red, 1=blue

int dfs(int node, int target, int lastColor, int length, int n) {
    if (node == target && length > 0) {
        return length;
    }
    
    int minLength = INT_MAX;
    
    // Try red edges if last edge wasn't red (lastColor != 0)
    if (lastColor != 0) {
        for (int i = 0; i < redCount[node]; i++) {
            int neighbor = redGraph[node][i];
            if (!visited[neighbor][0]) {
                visited[neighbor][0] = 1;
                int pathLength = dfs(neighbor, target, 0, length + 1, n);
                if (pathLength != -1 && pathLength < minLength) {
                    minLength = pathLength;
                }
                visited[neighbor][0] = 0;
            }
        }
    }
    
    // Try blue edges if last edge wasn't blue (lastColor != 1)
    if (lastColor != 1) {
        for (int i = 0; i < blueCount[node]; i++) {
            int neighbor = blueGraph[node][i];
            if (!visited[neighbor][1]) {
                visited[neighbor][1] = 1;
                int pathLength = dfs(neighbor, target, 1, length + 1, n);
                if (pathLength != -1 && pathLength < minLength) {
                    minLength = pathLength;
                }
                visited[neighbor][1] = 0;
            }
        }
    }
    
    return minLength == INT_MAX ? -1 : minLength;
}

int* solution(int n, int** redEdges, int redEdgesSize, int** blueEdges, int blueEdgesSize) {
    // Initialize graphs
    memset(redCount, 0, sizeof(redCount));
    memset(blueCount, 0, sizeof(blueCount));
    
    // Build red graph
    for (int i = 0; i < redEdgesSize; i++) {
        int u = redEdges[i][0];
        int v = redEdges[i][1];
        redGraph[u][redCount[u]++] = v;
    }
    
    // Build blue graph
    for (int i = 0; i < blueEdgesSize; i++) {
        int u = blueEdges[i][0];
        int v = blueEdges[i][1];
        blueGraph[u][blueCount[u]++] = v;
    }
    
    int* result = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        result[i] = -1;
    }
    result[0] = 0;
    
    // Find shortest path to each node
    for (int i = 1; i < n; i++) {
        memset(visited, 0, sizeof(visited));
        result[i] = dfs(0, i, -1, 0, n);
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Parse red edges (simplified)
    int** redEdges = NULL;
    int redEdgesSize = 0;
    
    // Parse blue edges (simplified)
    int** blueEdges = NULL;
    int blueEdgesSize = 0;
    
    int* result = solution(n, redEdges, redEdgesSize, blueEdges, blueEdgesSize);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", result[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^(E+V))

DFS explores all possible paths, potentially exponential combinations

✓ Linear Growth

Space Complexity

O(V)

Recursion stack depth up to V nodes plus visited array

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler