Skip to content

1129.shortest-path-with-alternating-colors.md

Latest commit

 

History

History
146 lines (122 loc) · 5.88 KB

1129.shortest-path-with-alternating-colors.md

File metadata and controls

146 lines (122 loc) · 5.88 KB

1129. Shortest Path with Alternating Colors

Hints

  • What if you ignore the color alternation? How would you find the shortest path?
  • How can you represent the state so that you don't revisit the same node with the same previous color?
  • Why do you need to track the color of the previous edge in your BFS state?

Breakdowns

  1. How to calculate the shortest path from 0 to i?

Start BFS from 0, and maintain a distance array for each node.

  1. How to know the color of the edge for node i?

Convert the edge lists to two adjacency lists: one for red edges, one for blue edges.

var red[i] = set(...)
var blue[i] = set(...)
  1. How to alternate color along the path?

Record the color of the previous edge in the BFS state, and only traverse edges of the opposite color next.

node.color = !node.color
  1. How to know there is no such path?

Initialize the distance as inf (or Int.MAX_VALUE), then if it remains inf after traversal, it is unreachable.

BFS with Color State

  • This is a classic BFS shortest path problem, but with an extra state: the color of the previous edge.
  • The key is to treat (node, previous color) as the BFS state, because you can revisit the same node if you arrive via a different color.
  • You need two visited arrays (or a 2D visited array): one for red, one for blue, to avoid revisiting the same node with the same color.
  • This pattern is similar to other BFS problems with extra state, such as 1293. Shortest Path in a Grid with Obstacles Elimination, where the state includes remaining eliminations.
  • BFS guarantees the shortest path is found first for each state.
data class MyNode(
    val index: Int,
    val isRed: Boolean, // true if the previous edge is red, false if blue
    val distance: Int
)

fun shortestAlternatingPaths(n: Int, redEdges: Array<IntArray>, blueEdges: Array<IntArray>): IntArray {
    // We conver to adjacency list or red and blue edges
    val redAdj = convert(n, redEdges)
    val blueAdj = convert(n, blueEdges)

    val distances = IntArray(n) { Int.MAX_VALUE }
    distances[0] = 0

    val queue = ArrayDeque<MyNode>()
    // We have to record the visited status for red and blue nodes separately
    // We can't use a single visited array, because we have to alternate the color
    val redVisited = BooleanArray(n)
    val blueVisited = BooleanArray(n)

    // Start from 0, and add the red and blue edges to the queue
    queue.addLast(MyNode(0, true, 0))
    queue.addLast(MyNode(0, false, 0))
    redVisited[0] = true
    blueVisited[0] = true

    // Or equivalently, we can add the red and blue edges to the queue
    // redAdj[0].forEach { i ->
    //     queue.addLast(MyNode(i, true, 1))
    //     redVisited[i] = true
    // }
    // blueAdj[0].forEach { i ->
    //     queue.addLast(MyNode(i, false, 1))
    //     blueVisited[i] = true
    // }

    // Regular BFS to update the shortest distance
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        val current = node.index
        val isRed = node.isRed
        val distance = node.distance

        // We update the distance for every node when visiting the particular node
        distances[current] = minOf(distances[current], distance)

        // Alternate the color for the adjacency nodes
        // Red -> Blue or Blue -> Red
        // distance + 1
        if (isRed) {
            blueAdj[current].forEach { adj ->
                if (blueVisited[adj].not()) {
                    queue.addLast(MyNode(adj, false, distance + 1))
                    blueVisited[adj] = true
                }
            }
        } else {
            redAdj[current].forEach { adj ->
                if (redVisited[adj].not()) {
                    queue.addLast(MyNode(adj, true, distance + 1))
                    redVisited[adj] = true
                }
            }
        }
    }
    // If the distance is still `inf`, then it is impossible to reach
    for (i in 0 until n) {
        if (distances[i] == Int.MAX_VALUE) distances[i] = -1
    }
    return distances
}

private fun convert(n: Int, edges: Array<IntArray>): Array<HashSet<Int>> {
    val adjArr = Array(n) { HashSet<Int>() }
    for (e in edges) {
        val from = e[0]
        val to = e[1]
        adjArr[from].add(to)
    }
    return adjArr
}
  • Time Complexity: O(N + Red + Blue), where N is the number of nodes, and Red/Blue are the number of red/blue edges.
  • Space Complexity: O(N + Red + Blue) for adjacency lists and visited arrays.

Edge Cases

  • If there are no outgoing edges from 0, all other nodes are unreachable.
  • If a node can only be reached by two consecutive edges of the same color, it is unreachable.
  • Self-loops and parallel edges: the algorithm handles them naturally, as long as you track visited by color.
  • If the graph is disconnected, unreachable nodes should return -1.

Pitfalls

  • Forgetting to track visited status separately for red and blue arrivals can lead to infinite loops or incorrect answers.
  • Not alternating colors correctly when traversing edges.
  • Updating the distance for a node without considering the color state can cause wrong results.
  • Mistake: Using a single visited array for all states (should be per color).
  • Mistake: Not initializing both red and blue starts from node 0.

Similar or Follow-up Problems