LeetCode 1129: Shortest Path with Alternating Colors Solution

Master LeetCode problem 1129 (Shortest Path with Alternating Colors), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1129. Shortest Path with Alternating Colors

Medium

Breadth-First Search Graph

Problem Explanation

Explanation

To solve this problem, we can use a breadth-first search (BFS) algorithm. We will maintain two queues, one for red edges and one for blue edges, to explore the graph alternatively based on the edge colors. We will keep track of the visited nodes and the distances from node 0 to each node with alternating colors. If we reach a node with the same color as the previous edge, we will ignore that edge.

Initialize two queues for red and blue edges, and a visited array to keep track of visited nodes.
Start with node 0 and add it to both red and blue queues with distances 0.
Process the nodes from the queues alternately based on their colors, updating distances in the answer array.
Skip the edge if it has the same color as the previous edge.
Continue until both queues are empty or we have processed all the nodes.

Time Complexity: O(n + m) where n is the number of nodes and m is the number of edges in the graph. Space Complexity: O(n)

Solution Code

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<Integer>[] redGraph = new ArrayList[n];
        List<Integer>[] blueGraph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            redGraph[i] = new ArrayList<>();
            blueGraph[i] = new ArrayList<>();
        }

        for (int[] edge : redEdges) {
            redGraph[edge[0]].add(edge[1]);
        }

        for (int[] edge : blueEdges) {
            blueGraph[edge[0]].add(edge[1]);
        }

        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        answer[0] = 0;

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0}); // Node, Color

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                int node = curr[0];
                int color = curr[1];

                for (int next : color == 0 ? redGraph[node] : blueGraph[node]) {
                    int nextColor = 1 - color; // Toggle color
                    if (answer[next] == -1) {
                        answer[next] = answer[node] + 1;
                        queue.offer(new int[]{next, nextColor});
                    }
                }
            }
        }

        return answer;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1129 (Shortest Path with Alternating Colors)?

This page provides optimized solutions for LeetCode problem 1129 (Shortest Path with Alternating Colors) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

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

The time complexity for LeetCode 1129 (Shortest Path with Alternating Colors) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1129 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1129 in Java, C++, or Python.

Back to LeetCode Solutions