🧠 What I Learned While Solving the “Shortest Path with Alternating Colors” Graph Problem

By Sai Pranav Moluguri

Recently, while working on the Shortest Path with Alternating Colors graph problem, I learned something that completely changed how I think about Breadth-First Search.

At first glance, the problem looked like another shortest path problem.

Naturally, BFS seemed like the right algorithm.

But after watching the NeetCode explanation and carefully understanding the solution, I realized that this wasn’t a standard BFS problem at all.

It introduced me to a new idea.

Sometimes, the state of your BFS is more than just the node you’re standing on.

Sometimes, the path you took to get there matters just as much.

That realization completely changed how I looked at graph traversals.

The First Realization

Normally, when I solve graph problems using BFS, my state looks like this:

queue = deque([0])
visited = {0}

Every node is visited exactly once.

Once I reach a node, I’m done with it.

That has been true for almost every graph problem I’ve solved so far.

But this problem quietly broke that assumption.

The Second Realization

Suppose I reach node 3.

Can I simply mark it as visited?

Surprisingly…

No.

Because reaching node 3 after taking a red edge is completely different from reaching node 3 after taking a blue edge.

If my previous edge was red, then my next edge must be blue.

If my previous edge was blue, then my next edge must be red.

That means these two situations are not the same:

(3, RED)

(3, BLUE)

They represent two completely different states.

For the first time, I realized that BFS doesn’t always operate on nodes alone.

Sometimes, it operates on states.

In this problem, the state is:

(node, previous_edge_color)

That was one of the biggest conceptual takeaways from this problem.

The Third Realization

Another elegant part of the solution was how the traversal naturally alternates between edge colors.

Instead of writing complicated logic, the algorithm simply says:

if previous_color != "RED":
    explore all RED edges

if previous_color != "BLUE":
    explore all BLUE edges

That’s it.

The alternation happens automatically.

I really liked how simple and readable this approach is.

Sometimes the cleanest solutions come from representing the right state instead of writing more conditions.

The Fourth Realization

One part of the solution surprised me.

The BFS starts like this:

queue = deque([
    (0, 0, "RED"),
    (0, 0, "BLUE")
])

At first, I wondered why we were starting from both colors.

Then it clicked.

The starting node has no previous edge.

So we pretend that we arrived at node 0 from both possibilities.

If we pretend the previous edge was red, the next edge must be blue.

If we pretend the previous edge was blue, the next edge must be red.

Starting from both states guarantees that we never miss a valid shortest path.

I thought that was a very elegant trick.

A Small Python Discovery That I Really Liked

While reading the solution, I also discovered something that made my Python code much cleaner.

For a long time, I built adjacency lists like this:

red = {}

for src, dst in redEdges:
    if src not in red:
        red[src] = []
    red[src].append(dst)

This works perfectly.

But the solution used something I hadn’t appreciated before:

from collections import defaultdict

red = defaultdict(list)

for src, dst in redEdges:
    red[src].append(dst)

That single line

red = defaultdict(list)

automatically creates an empty list whenever a new key is accessed.

Which means I no longer have to write:

if src not in red:
    red[src] = []

Even better, traversal becomes cleaner.

Instead of worrying whether a node exists inside the dictionary,

I can simply write:

for nei in red[node]:

If the node has no outgoing red edges,

defaultdict(list) simply returns an empty list.

The loop naturally executes zero times.

No extra conditions.

No get() calls.

No KeyError.

It’s a small optimization, but it makes graph code noticeably cleaner.

This was one of those Python features that I wish I had started using earlier.

My Final Implementation

from collections import defaultdict, deque

class Solution:
    def shortestAlternatingPaths(self, n, redEdges, blueEdges):
        red = defaultdict(list)
        blue = defaultdict(list)

        for src, dst in redEdges:
            red[src].append(dst)

        for src, dst in blueEdges:
            blue[src].append(dst)

        res = [-1] * n
        visited = set()

        q = deque([
            (0, 0, "RED"),
            (0, 0, "BLUE")
        ])

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

            if res[node] == -1:
                res[node] = dist

            visited.add((node, color))

            if color != "RED":
                for nei in red[node]:
                    if (nei, "RED") not in visited:
                        visited.add((nei, "RED"))
                        q.append((nei, dist + 1, "RED"))

            if color != "BLUE":
                for nei in blue[node]:
                    if (nei, "BLUE") not in visited:
                        visited.add((nei, "BLUE"))
                        q.append((nei, dist + 1, "BLUE"))

        return res

The Biggest Realization

After solving this problem, I realized that graph algorithms continue to teach me something deeper than just implementations.

Every new problem changes the way I think.

Earlier, I learned that some problems require Multi-Source BFS.

This problem taught me something different.

Sometimes, the state of a BFS isn’t just the node.

It can be the node combined with additional information that affects future decisions.

That extra piece of information completely changes how the search behaves.

Understanding that felt much more valuable than simply remembering another solution.

My Takeaway

This problem reinforced another important lesson in my DSA journey.

The hardest part isn’t writing code.

It’s identifying what information uniquely describes a state.

Once I recognized that the previous edge color was part of the state, the rest of the solution became surprisingly elegant.

I also walked away with a practical Python improvement.

Learning about defaultdict(list) made my graph implementations shorter, cleaner, and easier to read.

Sometimes, solving a problem teaches you an algorithm.

Other times, it teaches you a better way to think.

This problem did both.

About Me

I am Sai Pranav Moluguri, a recent Master’s graduate in Computer Science from Florida Atlantic University (FAU).

My interests include:

• Backend Development
• Full-Stack Engineering (MERN Stack)
• Distributed Systems & Scalable Architectures

I am currently preparing for Software Development Engineer opportunities while working toward my long-term goal of becoming a FAANG Software Engineer.

Forever Learning. Forever Growing.

— Sai Pranav Moluguri