Shortest alternate colored path
Consider a directed graph of ‘N’ nodes where each node is labeled from ‘0’ to ‘N - 1’. Each edge of the graph is either ‘red’ or ‘blue’ colored. The graph may contain self-edges or parallel edges. You are given two arrays, ‘redEdges’ and ‘blueEdges’, whose each element is of the form [i, j], denoting an edge from node ‘i’ to node ‘j’ of the respective color.

Your task is to compute an array ‘answer’ of size ‘N’, where ‘answer[i]’ stores the length of the shortest path from node ‘0’ to node ‘i’ such that the edges along the path have alternate colors. If there is no such path from node ‘0’ to ‘i’, then ‘answer[i] = -1’.

Example:

N = 4, redEdges = [[0, 1], [2, 3]], blueEdges = [[1, 2], [1, 3]]

The shortest paths for each node from node ‘0’ are: 1: 0-1 Length: 1 2: 0-1-2 Length: 2 3: 0-1-3 Length: 2 So, the ‘answer’ array will be: [0, 1, 2, 2].

Note:

1. The given graph could be a disconnected graph. 2. Any two nodes ‘i’ and ‘j’ can have at most one red edge from ‘i’ to ‘j’ and at most one blue edge from ‘i’ to ‘j’.

Input format:

The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow. The first line of each test case contains three space-separated integers ‘N’, ‘rlen’, and ‘blen’ denoting the number of nodes in the graph, the size of array ‘redEdges’, and the size of array ‘blueEdges’. The next 'rlen' lines of each test case contain two space-separated integers, ‘i’ and ‘j’ denoting a ‘red’ edge from node ‘i’ to node ‘j’. The next 'blen' lines of each test case contain two space-separated integers, ‘i’ and ‘j’ denoting a ‘blue’ edge from node ‘i’ to node ‘j’.

Output format:

For every test case, print a single line containing N space-separated integers denoting array ‘answer’, where ‘answer[i]’ contains the valid shortest path length from node ‘0’ to node ‘i’. The output for each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Shortest alternate colored path

Consider a directed graph of ‘N’ nodes where each node is labeled from ‘0’ to ‘N - 1’. Each edge of the graph is either ‘red’ or ‘blue’ colored. The graph may contain self-edges or parallel edges. You are given two arrays, ‘redEdges’ and ‘blueEdges’, whose each element is of the form [i, j], denoting an edge from node ‘i’ to node ‘j’ of the respective color.

Your task is to compute an array ‘answer’ of size ‘N’, where ‘answer[i]’ stores the length of the shortest path from node ‘0’ to node ‘i’ such that the edges along the path have alternate colors. If there is no such path from node ‘0’ to ‘i’, then ‘answer[i] = -1’.

Example:

N = 4, redEdges = [[0, 1], [2, 3]], blueEdges = [[1, 2], [1, 3]]

example

The shortest paths for each node from node ‘0’ are:
1: 0->1         Length: 1
2: 0->1->2      Length: 2
3: 0->1->3      Length: 2
So, the ‘answer’ array will be: [0, 1, 2, 2].

Note:

1. The given graph could be a disconnected graph.

2. Any two nodes ‘i’ and ‘j’ can have at most one red edge from ‘i’ to ‘j’ and at most one blue edge from ‘i’ to ‘j’.

Input format:

The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains three space-separated integers ‘N’, ‘rlen’, and ‘blen’ denoting the number of nodes in the graph, the size of array ‘redEdges’, and the size of array ‘blueEdges’.

The next 'rlen' lines of each test case contain two space-separated integers, ‘i’ and ‘j’ denoting a ‘red’ edge from node ‘i’ to node ‘j’.

The next 'blen' lines of each test case contain two space-separated integers, ‘i’ and ‘j’ denoting a ‘blue’ edge from node ‘i’ to node ‘j’.

Output format:

For every test case, print a single line containing N space-separated integers denoting array ‘answer’, where ‘answer[i]’ contains the valid shortest path length from node ‘0’ to node ‘i’. 

The output for each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 100
1 <= N <= 200
0 <= rlen + blen <= 1000

Where ‘T’ is the number of test cases, ‘N’ is the number of nodes in the graph, ‘rlen’ is the size of array ‘redEdges’, and ‘blen’ is the size of array ‘blueEdges’.

Time limit: 1 second

Accepted Answer

Modified Dijkstra’s algorithm

Dijkstra’s algorithm is used for finding the shortest path between nodes in a weighted graph. As the given graph is unweighted, the path length is equal to the number of edges, so consider each edge’s weight to be ‘1’. The maximum shortest path length will be ‘2*n - 3’, which will be achieved when all edges from node ‘i’ to ‘j’ (where ‘i != j’) have the same color ‘red’ and each node has a self-loop of ‘blue’ color or vice-versa.

For any node ‘x’ a valid path can be of two forms:

0 -> ... -’blue edge’-> x. (Ending with blue edge)
0 -> … -’red edge’-> x. (Ending with red edge)

Create two graphs ‘graph[2][n]’, the first ‘graph[0]’ containing red edges and the second ‘graph[1]’ containing blue edges. Here, ‘graph[i][j][k]’ means an edge of color type ‘i’ (‘0’ is red and ‘1’ is blue) from node ‘j’ to node ‘k’. A node can be represented in the form ‘[x, c]’ where ‘x’ is the node’s label and ‘c’ is the color of the incoming edge. Use a 2-d array ‘dist[n][2]’, where ‘dist[i][0]’ will store the length of the shortest path to reach node ‘i’ from a red edge and ‘dist[i][1]’ is the length with a blue edge. Use a 2-d array ‘sptSet[n][2]’ to check if we have found the shortest path for a node of form ‘[x, c]’.

Initialize the array ‘dist’ with value ‘2*n’ (i.e., unreachable from node ‘0’). Set ‘dist[0][0] = dist[0][1] = 0’ i.e., node ‘0’ is reachable from both blue and red edges with a path of zero length. Set ‘sptSet[0][0] = sptSet[0][1] = 0’, which means the length of shortest path to reach node ‘[0, 0]’ and ‘[0, 1]’ is zero.

Now, use Dijkstra’s shortest path algorithm to find the shortest path length for each such node ‘[x, c]’ from node ‘0’ (i.e., from ‘[0, 0]’ and ‘[0, 1]’). Let ‘minDist’ be the set of nodes (with their path length) that are reachable from the nodes in ‘sptSet’. Initially, both ‘sptSet’ and ‘minDist’ contain two nodes, ‘[0, 0]’ and ‘[0, 1]’, the source nodes.

According to Dijkstra’s algorithm:

In each iteration, remove the node (let’s say ‘[x, c]’) having the smallest path length in ‘minDist’ (let’s say ‘len’). Then ‘len’ is the shortest path length for node ‘[x, c]’ from node ‘0’. Set ‘sptSet[x][c] = true’ and ‘dist[x][c] = len’ as we have found it’s shortest path length. For all the nodes that are reachable from ‘[x, c]’, if they have ‘sptSet’ as false (i.e., their shortest path is not known) and their ‘dist’ value is larger than ‘dist[x][c] + 1’ then, add them to the set ‘minDist’ and update their ‘dist’ value. Stop the iteration when the set ‘minDist’ becomes empty, i.e., when we have found the shortest path for all nodes reachable from node ‘0’ (the source node).

Finally, for each node ‘i’ we have ‘answer[i] = min(dist[i][0], dist[i][1])’. If ‘answer[i]’ is still ‘2*n’ then no valid path exists to reach node ‘i’, set ‘answer[i] = -1’. Use a Priority Queue to implement ‘minDist’, so that we can extract the smallest element efficiently (in ‘O(log(n))’). Below is an implementation of Dijkstra’s algorithm using priority queue:

Create an array of list ‘graph[2][n]’ to store the given graph.
Run a loop where ‘i’ ranges from ‘0’ to ‘length(redEdges) - 1’:
- ‘graph[0][redEdges[i][0]].append(redEdges[i][1])’
Run a loop where ‘i’ ranges from ‘0’ to ‘length(blueEdges) - 1’:
- ‘graph[1][blueEdges[i][0]].append(blueEdges[i][1])’
Create a min priority queue ‘minDist’ that stores ‘Node’ objects and orders them by ‘Node->dist’. A ‘Node’ contains three values {‘dist’, ‘label’, ‘color’}.
Insert {0, 0, 0} and {0, 0, 1} in ‘minDist’. These are the source nodes, [0, 0] and [0, 1] with ‘dist’ equal to zero.
Initialize array ‘dist[n][2]’ with value ‘2*n’.
Set ‘dist[0][0] = dist[0][1] = 0’ (for source nodes).
Run a loop until ‘minDist’ is not empty:
- ‘node = minDist.pop()’. Get the node with the smallest known distance and remove it from ‘minDist’.
- ‘cur = node->label’. The current node label.
- ‘c = node->color’. The color of the incoming edge.
- If ‘dist[cur][c] < (node->dist)’ then, ignore this node as it doesn’t have the minimum distance:
  - Continue the loop.
- Run a loop where ‘i’ ranges from ‘0’ to ‘length(graph[1 - c][cur]) - 1’
  - ‘next = graph[1 - c][cur][i]’. Move to the neighboring node through an edge of color ‘1 - c’, i.e., alternate of color ‘c’.
  - If ‘dist[next][1 - c] > dist[next][c] + 1’, then:
    - ‘dist[next][1 - c] = dist[next][c] + 1’
    - ‘minDist.push({dist[next][1 - c], next, 1- c})’. Push an ‘Node’ object to ‘minDist’.
Create an array ‘answer[n]’ to store the answer.
Run a loop where ‘i’ ranges from ‘0’ to ‘n - 1’:
- ‘answer[i] = min(dist[i][0], dist[i][1])’
- If ‘answer[i] = 2*n’, then:
  - ‘answer[i] = -1’
Return the array ‘answer’ as the final answer.

Space Complexity: OtherExplanation:

O(RLEN + BLEN + N), where 'RLEN' is the number of red edges, 'BLEN' is the number of blue edges, and ‘N’ is the number of nodes.

We create an adjacency list for the given graph, which takes ‘O(RLEN + BLEN)’ space. The array ‘DIST’ takes ‘O(N)’ space, and the priority queue stores ‘O(RLEN + BLEN)’ elements at most. Hence, the space complexity is ‘O(RLEN + BLEN + N)’.

Time Complexity: OtherExplanation:

O(N + (RLEN + BLEN) * log(RLEN + BLEN)), where ‘RLEN’ is the number of red edges, ‘BLEN’ is the number of blue edges, and ‘N’ is the number of nodes.

Whenever a node’s distance is reduced, we add that instance of the node in the priority queue. Therefore, there can be multiple instances, but we only consider the instance with the minimum distance and ignore others. So, there can be at most ‘O(E)’ vertices (one for each edge) in the priority queue, hence the time complexity ‘O(E * log(E))’. Creating the ‘DIST’ to store the shortest path for each node array takes ‘O(N)’ time. As the number of edges in the graph ‘E = RLEN+ BLEN’, total time complexity is ‘O(N + (RLEN+ BLEN) * log(RLEN + BLEN))'.

Java (SE 1.8)

/*

    Time Complexity : O(N + (RLEN + BLEN) * log(RLEN + BLEN))

    Space Complexity : O(N + RLEN + BLEN)



    where 'RLEN' is the number of red edges, 

	'BLEN' is the number of blue Edges and 'N' is the number of nodes.

*/



import java.util.ArrayList;

import java.util.PriorityQueue;



// Structure of 'Node' used in priority queue.

class Node implements Comparable {

	int dist;

	int label;

	int color;



	Node(int dist, int label, int color) {

		this.dist = dist;

		this.label = label;

		this.color = color;

	}



	public int compareTo(Node o) {

		return o.dist - dist;

	}

}



public class Solution {



	public static ArrayList shortestAlternateColoredPath(int n, int[][] redEdges, int[][] blueEdges) {

		ArrayList[][] graph = new ArrayList[2][n];

		for (int i = 0; i < n; i++) {

			graph[0][i] = new ArrayList();

			graph[1][i] = new ArrayList();

		}



		for (int i = 0; i < redEdges.length; i++) {



			// Add red edges to 'graph[0]'.

			graph[0][redEdges[i][0]].add(redEdges[i][1]);

		}

		for (int i = 0; i < blueEdges.length; i++) {



			// Add blue edges to 'graph[1]'.

			graph[1][blueEdges[i][0]].add(blueEdges[i][1]);

		}



		int[][] dist = new int[n][2];

		for (int i = 0; i < n; i++) {

			dist[i][0] = 2 * n;

			dist[i][1] = 2 * n;

		}



		dist[0][0] = dist[0][1] = 0;



		PriorityQueue minDist = new PriorityQueue<>();

		minDist.add(new Node(0, 0, 0));



		// Source node with red incoming edge.

		minDist.add(new Node(0, 0, 1));



		// Source node with blue incoming edge.

		while (!minDist.isEmpty()) {

			Node node = minDist.peek();

			minDist.remove();



			int cur = node.label;

			int c = node.color;



			// If the path length of [cur, c] in 'node' is greater than 'dist[cur][c]' skip this node.

			if (dist[cur][c] < node.dist)

				continue;



			for (int i = 0; i < graph[1 - c][cur].size(); i++) {

				int next = graph[1 - c][cur].get(i);



				if (dist[next][1 - c] > dist[cur][c] + 1) {

					dist[next][1 - c] = dist[cur][c] + 1;

					minDist.add(new Node(dist[next][1 - c], next, 1 - c));

				}

			}

		}



		ArrayList answer = new ArrayList<>(n);

		for (int i = 0; i < n; i++) {

			answer.add(i);

		}



		for (int i = 0; i < n; i++) {

			// Compute the array 'answer' from 'dist'.

			answer.set(i, Math.min(dist[i][0], dist[i][1]));

			if (answer.get(i) == 2 * n)

				answer.set(i, -1);

		}



		return answer;

	}

}

C++ (g++ 5.4)

/*

    Time Complexity : O(N + (RLEN + BLEN) * log(RLEN + BLEN))

    Space Complexity : O(N + RLEN + BLEN)



    where 'RLEN' is the number of red edges, 

	'BLEN' is the number of blue Edges and 'N' is the number of nodes.

*/



#include 



// Structure of 'Node' used in priority queue.

struct Node 

{

    int dist;

    int label;

    int color;

    bool operator<(const Node& a) const 

	{  

        return a.dist < dist;    

    }

};



vector shortestAlternateColoredPath(int n, vector>& redEdges, vector>& blueEdges) 

{

    vector graph[2][n];



    for (int i = 0; i < redEdges.size(); i++) 

	{

        graph[0][redEdges[i][0]].push_back(redEdges[i][1]);

    }

    for (int i = 0; i < blueEdges.size(); i++) 

	{  

		// Add blue edges to 'graph[1]'.

        graph[1][blueEdges[i][0]].push_back(blueEdges[i][1]);

    }



    vector> dist(n, vector(2, 2 * n));

    dist[0][0] = dist[0][1] = 0;  



    priority_queue minDist;

    minDist.push({0, 0, 0});  

	// Source node with red incoming edge.

    minDist.push({0, 0, 1});  

	// Source node with blue incoming edge.



    while (!minDist.empty()) 

	{

        Node node = minDist.top();

        minDist.pop();



        int cur = node.label; 

        int c = node.color;    



        // If the path length of [cur, c] in 'node' is greater than 'dist[cur][c]' skip this node.

        if (dist[cur][c] < node.dist) continue;



        for (int i = 0; i < graph[1 - c][cur].size(); i++) 

		{

            int next = graph[1 - c][cur][i];  



            if (dist[next][1 - c] > dist[cur][c] + 1) 

			{

                dist[next][1 - c] = dist[cur][c] + 1;

                minDist.push({dist[next][1 - c], next, 1 - c});

            }

        }

    }



    vector answer(n);

    for (int i = 0; i < n; i++) 

	{  

		// Compute the array 'answer' from 'dist'.

        answer[i] = min(dist[i][0], dist[i][1]);

        if (answer[i] == 2 * n) answer[i] = -1;

    }



    return answer;

}

Python (3.5)

'''

    Time Complexity : O(N + (RLEN + BLEN) * log(RLEN + BLEN))

    Space Complexity : O(N + RLEN + BLEN)



    where 'RLEN' is the number of red edges, 

    'BLEN' is the number of blue Edges and 'N' is the number of nodes.

'''



from queue import Queue



def shortestAlternateColoredPath(n, redEdges, blueEdges):



    graph = []

    red = []

    blue = []

    for i in range(n):

        red.append([])

        blue.append([])

    graph.append(red)

    graph.append(blue)



    for i in range(len(redEdges)):



        # Add red edges to 'graph[0]'.

        graph[0][redEdges[i][0]].append(redEdges[i][1])



    for i in range(len(blueEdges)):



        # Add blue edges to 'graph[1]'.

        graph[1][blueEdges[i][0]].append(blueEdges[i][1])



    dist = []

    for i in range(n):



        temp = [2*n, 2*n]



        dist.append(temp)



    dist[0][0] = dist[0][1] = 0  



    minDist = Queue(maxsize=10**5)



    minDist.put([0, 0, 0]) 

    # Source node with blue incoming edge.

    minDist.put([0, 0, 1])  



    while (not minDist.empty()):



        node = minDist.get()



        cur = node[1]  

        c = node[2]    



        # If the path length of [cur, c] in 'node' is greater than 'dist[cur][c]' skip this node.

        if (dist[cur][c] < node[0]):

            continue



        for i in range(len(graph[1-c][cur])):



            # Neighboring node with alternate color edge.

            next = graph[1 - c][cur][i]



            if (dist[next][1 - c] > dist[cur][c] + 1):

                dist[next][1 - c] = dist[cur][c] + 1

                minDist.put([dist[next][1 - c], next, 1 - c])



    answer = [0]*n



    # Compute the array 'answer' from 'dist'.

    for i in range(n):

        answer[i] = min(dist[i][0], dist[i][1])

        if (answer[i] == 2 * n):

            answer[i] = -1



    return answer

Accepted Answer

Use Breadth-first search algorithm

Since the given graph is unweighted, we can find the shortest path for each node in ‘O(E + V)’ = ‘O(rlen+blen+ n)’ time using a modified Breadth-first search algorithm. Similar to the previous approach, we create two separate graphs for ‘redEdges’ and ‘blueEdges’. Consider ‘2 * n’ nodes of the form ‘[x, c]’ where ‘x’ is the node label, and ‘c’ is the color of the incoming edge.

Create an array ‘dist[n][2]’, where ‘dist[x][c]’ stores the length of shortest path for node ‘[x, c]’ where ‘c = 0’ means red edge and ‘c = 1’ means blue edge. Except for node ‘0’ set ‘dist[i][j]’ as ‘2 * n’ (as maximum possible length of valid path is ‘2 * n - 3’). We know the distance of nodes ‘[0, 0]’ and ‘[0, 1]’ is equal to zero, the base condition for source node ‘0’. Initially, the BFS queue contains these two nodes. Run a loop until the BFS queue is not empty. In each iteration, the current node is popped from the front of the queue. As we reach the current node(let’s say ‘[x, c]’) from an edge of color ‘c’, the next reachable node must be from an opposite edge color (‘1 - c’). For each node that is reachable from ‘[x, c]’, if its distance in ‘dist’ is greater than of ‘dist[x][c] + 1’ then, update its distance value in ‘dist’ and push this node at the end of the BFS queue.

Proof of correctness: As we move level-wise in BFS, if a child node is not visited, it’s not reachable from any previous levels. Its shortest path will be equal to (parent node’s level + 1). Even if it’s reachable from any other node from the next levels, the corresponding path length will always be greater.

Following is a BFS implementation to solve this problem:

Create an array of list ‘graph[2][n]’ to store the given graph.
Run a loop where ‘i’ ranges from ‘0’ to ‘length(redEdges) - 1’:
- ‘graph[0][redEdges[i][0]].append(redEdges[i][1])’
Run a loop where ‘i’ ranges from ‘0’ to ‘length(blueEdges) - 1’:
- ‘graph[1][blueEdges[i][0]].append(blueEdges[i][1])’
Initialize array ‘dist[n][2]’ with value ‘2*n’. Use ‘dist[x][c]’ to store the length of shortest path for the node ‘[x, c]’,where ‘x’ is the node label and ‘c’ is the incoming edge color.
Set ‘dist[0][0] = dist[0][1] = 0’ (for source nodes).
Create a queue ‘bfsQ’ to perform BFS on the given graph.
Push ‘[0, 0]’ and ‘[0, 1]’ in ‘bfsQ’. These are the source nodes.
Run a loop while ‘bfsQ’ is not empty:
- ‘[x, c] = bfsQ.pop()’.
- Run a loop where ‘i’ ranges from ‘0’ to ‘length(graph[x][1 - c])’:
  - ‘next = graph[x][1 - c][i]’
  - If ‘dist[next][1 - c] > dist[x][c] + 1’, then:
    - ‘dist[next][1 - c] = dist[x][c] + 1’
    - ‘bfsQ.push([next, 1 - c])’
Create an array ‘answer[n]’ to store the answer.
Run a loop where ‘i’ ranges from ‘0’ to ‘n - 1’:
- ‘answer[i] = min(dist[i][0], dist[i][1])’. Get the minimum from the shortest path having red or blue incoming edges.
- If ‘answer[i] = 2*n’, then this node is not reachable through a valid sequence of edges, so:
  - ‘answer[i] = -1’
Return the array ‘answer’ as the final answer.

Space Complexity: OtherExplanation:

O(N + RLEN + BLEN), where 'RLEN' is the number of red edges, 'BLEN' is the number of blue edges, and ‘N’ is the number of nodes.

We create an adjacency list for the given graph, which takes ‘O(RLEN + BLEN)’ space. The array ‘DIST’ takes ‘O(N)’ space, and the BFS queue stores ‘O(N)’ elements at most. Hence, the space complexity is ‘O(N + RLEN + BLEN)'.

Time Complexity: OtherExplanation:

O(N + RLEN + BLEN), where 'RLEN' is the number of red edges, and 'BLEN' is the number of blue edges, and ‘N’ is the number of nodes.

Creating the ‘DIST’ array takes ‘O(N)’ time. To compute the shortest path, we visit each edge once, taking ‘O(E)’ time. As the number of edges in the graph ‘E = RLEN + BLEN’, the total time complexity is ‘O(N + RLEN + BLEN)’.

Java (SE 1.8)

/*

    Time Complexity : O(N + RLEN + BLEN)

    Space Complexity : O(N + RLEN + BLEN)



    where 'RLEN' is the number of red edges, 

	'BLEN' is the number of blue Edges and 'N' is the number of nodes.

*/



import java.util.*;



public class Solution {

    public static ArrayList shortestAlternateColoredPath(int n, int redEdges[][], int blueEdges[][]) {

        

        ArrayList[][] graph = new ArrayList[2][n];

        for (int i = 0; i < n; i++) {

            graph[0][i] = new ArrayList();

            graph[1][i] = new ArrayList();

        }



        for (int i = 0; i < redEdges.length; i++) {  

			// Add red edges to 'graph[0]'.

            graph[0][redEdges[i][0]].add(redEdges[i][1]);

        }

        for (int i = 0; i < blueEdges.length; i++) {  

			// Add blue edges to 'graph[1]'.

            graph[1][blueEdges[i][0]].add(blueEdges[i][1]);

        }



        int[][] dist = new int[n][2];

        for (int i = 0; i < n; i++) {

            dist[i][0] = 2 * n;

            dist[i][1] = 2 * n;

        }

        

        dist[0][0] = dist[0][1] = 0;  



        Queue bfsQ = new LinkedList();

        bfsQ.add(new Pair(0, 0));  

        bfsQ.add(new Pair(0, 1));  



        while (!bfsQ.isEmpty()) {

            int x = bfsQ.peek().first;   

            int c = bfsQ.peek().second;  

            bfsQ.poll();



            for (int i = 0; i < graph[1 - c][x].size(); i++) {

                int next = graph[1 - c][x].get(i);  

				// Neighboring node with alternate color edge.



                if (dist[next][1 - c] > dist[x][c] + 1) {

                    dist[next][1 - c] = dist[x][c] + 1;

                    bfsQ.add(new Pair(next, 1 - c));

                }

            }

        }



        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {  

			// Compute the array 'answer' from 'dist'.

            answer[i] = (int) (Math.min(dist[i][0], dist[i][1]));

            if (answer[i] == 2 * n) {

                answer[i] = -1;

            }

        }

		

        ArrayList ans = new ArrayList();

        for (int ele : answer) {

            ans.add(ele);

        }

        return ans;

    }

}

class Pair {

    int first, second;

    

    Pair(int x, int y) {

        first = x;

        second = y;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity : O(N + RLEN + BLEN)

    Space Complexity : O(N + RLEN + BLEN)



    where 'RLEN' is the number of red edges, 

	'BLEN' is the number of blue Edges and 'N' is the number of nodes.

*/



#include 



vector shortestAlternateColoredPath(int n, vector>& redEdges, vector>& blueEdges) 

{

    vector graph[2][n];



    for (int i = 0; i < redEdges.size(); i++) 

	{

        graph[0][redEdges[i][0]].push_back(redEdges[i][1]);

    }

    for (int i = 0; i < blueEdges.size(); i++) 

	{

        graph[1][blueEdges[i][0]].push_back(blueEdges[i][1]);

    }



    vector> dist(n, vector(2, 2 * n));

    dist[0][0] = dist[0][1] = 0;  



    queue> bfsQ;

	// Source node with red incoming edge.

    bfsQ.push(make_pair(0, 0));  

	// Source node with blue incoming edge.

    bfsQ.push(make_pair(0, 1));  



    while (!bfsQ.empty()) 

	{

        int x = bfsQ.front().first;  

        int c = bfsQ.front().second; 

        bfsQ.pop();



        for (int i = 0; i < graph[1 - c][x].size(); i++) 

		{

            int next = graph[1 - c][x][i];  

			// Neighboring node with alternate color edge.



            if (dist[next][1 - c] > dist[x][c] + 1) 

			{

                dist[next][1 - c] = dist[x][c] + 1;

                bfsQ.push(make_pair(next, 1 - c));

            }

        }

    }



    vector answer(n);

    for (int i = 0; i < n; i++) 

	{  

		// Compute the array 'answer' from 'dist'.

        answer[i] = min(dist[i][0], dist[i][1]);

        if (answer[i] == 2 * n) answer[i] = -1;

    }



    return answer;

}

Python (3.5)

'''

    Time Complexity : O(N + RLEN + BLEN)

    Space Complexity : O(N + RLEN + BLEN)



    where 'RLEN' is the number of red edges, 

    'BLEN' is the number of blue Edges and 'N' is the number of nodes.

'''



from queue import Queue



def shortestAlternateColoredPath( n,  redEdges,  blueEdges):

    

    graph =[]

    red=[]

    blue=[]

    for i in range(n):

        red.append([])

        blue.append([])

    graph.append(red)

    graph.append(blue)

    

    

    for i in range(len(redEdges)):

        

        # Add red edges to 'graph[0]'.

        graph[0][redEdges[i][0]].append(redEdges[i][1])

    

    

    for i in range(len(blueEdges)):

        

        # Add blue edges to 'graph[1]'.

        graph[1][blueEdges[i][0]].append(blueEdges[i][1])



    dist=[]

    for i in range(n):

        

        temp=[2*n, 2*n]

        

        dist.append(temp)

    

    dist[0][0] = dist[0][1] = 0 



    

    

    

    bfsQ = Queue(maxsize=10**5)

    bfsQ.put([0, 0])   

    bfsQ.put([0, 1])   



    while (not bfsQ.empty()):

        

        node= bfsQ.get()

        x = node[0]  

        c = node[1]  



            

        for i in range(len(graph[1-c][x])):

            

            next = graph[1 - c][x][i]    



            if (dist[next][1 - c] > dist[x][c] + 1):

                dist[next][1 - c] = dist[x][c] + 1

                bfsQ.put([next, 1 - c])

    



    

    answer=[0]*n

           

    # Compute the array 'answer' from 'dist'.                     

    for i in range(n):

        

        answer[i] = min(dist[i][0], dist[i][1])

        if (answer[i] == 2 * n):

            answer[i] = -1

            

    return answer

Accepted Answer

from collections import deque, defaultdict

def shortest_alternating_paths(N, redEdges, blueEdges):
    # Initialize the graph with adjacency lists
    red_graph = defaultdict(list)
    blue_graph = defaultdict(list)
    
    for u, v in redEdges:
        red_graph[u].append(v)
    for u, v in blueEdges:
        blue_graph[u].append(v)
    
    # Initialize the answer array with -1
    answer = [-1] * N
    answer[0] = 0
    
    # Queue for BFS: (node, color, distance)
    queue = deque([(0, 'red', 0), (0, 'blue', 0)])
    
    # Visited states: visited[node][0] for red, visited[node][1] for blue
    visited = [[False, False] for _ in range(N)]
    visited[0][0] = visited[0][1] = True
    
    while queue:
        node, color, distance = queue.popleft()
        
        # Determine the next color and graph to use
        if color == 'red':
            next_color = 'blue'
            next_graph = blue_graph
            color_idx = 1
        else:
            next_color = 'red'
            next_graph = red_graph
            color_idx = 0
        
        for neighbor in next_graph[node]:
            if not visited[neighbor][color_idx]:
                visited[neighbor][color_idx] = True
                queue.append((neighbor, next_color, distance + 1))
                
                if answer[neighbor] == -1:
                    answer[neighbor] = distance + 1
    
    return answer

def solve_test_cases(T, test_cases):
    results = []
    for t in range(T):
        N, rlen, blen, redEdges, blueEdges = test_cases[t]
        result = shortest_alternating_paths(N, redEdges, blueEdges)
        results.append(" ".join(map(str, result)))
    return results

# Example usage with multiple test cases:
T = 1
test_cases = [
    (4, 2, 2, [[0, 1], [2, 3]], [[1, 2], [1, 3]]),
    # You can add more test cases here
]

results = solve_test_cases(T, test_cases)
for result in results:
    print(result)

Your task is to compute an array ‘answer’ of size ‘N’, where ‘answer[i]’ stores the length of the shortest path from node ‘0’ to node ‘i’ such that the edges along the path have alternate colors. If there is no such path from node ‘0’ to ‘i’, then ‘answer[i] = -1’.

Example:

Note:

Input format:

Output format:

Note:

Constraints:

Top Flipkart Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Flipkart Software Developer