Intro to graphs: Flight service checker

You're sitting in your interview at a travel tech company when the interviewer pulls up a map of airline routes. "We have a network of airports connected by flights," they say. "Given an origin and destination, can you figure out whether it's possible to get from A to B, even with layovers?" This is a classic introduction to graph traversal, and it is also known as "Find if Path Exists in Graph" on other platforms. It tests your ability to model real-world relationships as graph data structures and navigate them efficiently.

TL;DR

Model the flight network as a directed graph using an adjacency list. Use BFS (or DFS) to explore airports starting from the origin, maintaining a visited set to avoid revisiting airports in cycles. If you dequeue the destination, return true. If the queue empties without finding it, return false. This runs in O(V + E) time and O(V) space.

Why This Problem Matters

Graph problems are among the most common topics in technical interviews, and this is one of the gentlest entry points. It introduces three fundamental concepts at once: graph representation via adjacency lists, graph traversal via BFS, and cycle avoidance via a visited set. Once you internalize this pattern, you can tackle harder graph problems like detecting cycles, topological sorting, and shortest path algorithms with confidence.

Graphs and Adjacency Lists: A Quick Primer

A graph is a collection of nodes (also called vertices) connected by edges. Unlike trees, graphs can have cycles, multiple paths between nodes, and nodes with no parent-child hierarchy.

The graph in this problem represents airport connections. Each node is an airport code, and each directed edge represents a non-stop flight. "Directed" means flights are one-way: just because you can fly SFO to AUS doesn't mean there's a return flight from AUS to SFO.

There are several ways to represent a graph in code. The most common for sparse graphs is an adjacency list, which maps each node to a list of its neighbors. For our flight network:

{
  "SFO": ["AUS", "MIA", "JFK"],
  "JFK": ["MIA", "TPA"],
  "AUS": ["IAH"],
  "IAH": ["AUS"],
  "TPA": ["JFK"]
}

Notice that MIA has no entry as a key because there are no outbound flights from MIA in this network. The adjacency list uses O(V + E) space, where V is the number of airports and E is the number of flight routes.

Understanding the Problem

Given: A directed graph as an adjacency list (origin airport to list of non-stop destinations), an origin airport code, and a destination airport code.

Return: true if you can fly from the origin to the destination, either non-stop or through connecting hubs. false otherwise.

Let's look at the examples from the problem:

1. flightCheck(G, "SFO", "IAH") returns true because you can fly SFO to AUS, then AUS to IAH.
2. flightCheck(G, "TPA", "MIA") returns true because you can fly TPA to JFK, then JFK to MIA.
3. flightCheck(G, "AUS", "MIA") returns false because from AUS you can only reach IAH (and IAH leads back to AUS), with no path to MIA.

Why a Simple Lookup Won't Work

You might be tempted to just check if the destination appears in the origin's neighbor list. That would handle non-stop flights, but it misses connecting routes. SFO doesn't have a direct flight to IAH, but you can get there through AUS. We need to explore the graph systematically.

The Cycle Trap

Here is the critical insight for graphs versus trees. Look at AUS and IAH in our flight network: AUS flies to IAH, and IAH flies back to AUS. If you naively follow every edge, you will bounce between these two airports forever. This is why we need a visited set to track airports we have already processed.

Solution Approach

The strategy is straightforward: start at the origin, explore all reachable airports one hop at a time, and check if we ever reach the destination. This is textbook BFS.

The BFS Algorithm

1. Create a Set to track visited airports and a Queue for BFS.
2. Enqueue the origin airport.
3. While the queue is not empty:
   • Dequeue an airport.
   • If it matches the destination, return true.
   • If we haven't visited this airport, mark it as visited and enqueue all of its neighbors.
4. If the queue empties without finding the destination, return false.

Tracing Through: SFO to IAH

Let's walk through the BFS for flightCheck(G, "SFO", "IAH"):

The path BFS discovers is SFO to AUS to IAH. Here is that path highlighted on the graph:

Tracing Through: AUS to MIA (No Path)

Now let's see what happens with flightCheck(G, "AUS", "MIA"):

1. Start with queue = [AUS], visited = {}
2. Poll AUS, not MIA, mark visited. AUS's neighbors: [IAH]. Queue = [IAH], visited = {AUS}
3. Poll IAH, not MIA, mark visited. IAH's neighbors: [AUS]. But AUS is already visited, so nothing new is enqueued. Queue = [], visited = {AUS, IAH}
4. Queue is empty. Return false.

From AUS, you can only reach IAH, and from IAH you loop back to AUS. The visited set prevents the infinite cycle, and BFS correctly determines there is no path to MIA.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

public class Solution {
  public Boolean flightCheck(
    Map<String, List<String>> originDestinationsMap,
    String origin,
    String destination
  ) {
    // Track airports we've already explored
    Set<String> visited = new HashSet<>();
    // BFS queue starting from the origin
    Queue<String> queue = new LinkedList<>();
    queue.offer(origin);

    while (!queue.isEmpty()) {
      String airportCode = queue.poll();

      // Found the destination
      if (airportCode.equals(destination)) return true;

      // Only process unvisited airports
      if (!visited.contains(airportCode)) {
        visited.add(airportCode);
        originDestinationsMap.getOrDefault(airportCode, List.of())
          .forEach(queue::offer);
      }
    }

    return false;
  }
}

A few things worth noting about the implementation:

• getOrDefault(airportCode, List.of()) handles the case where an airport has no outbound flights. Without this, you'd get a NullPointerException for airports like MIA that aren't keys in the map.
• We check the visited set after polling from the queue rather than before enqueuing. Both approaches work, but checking after polling is slightly simpler. Checking before enqueuing is more memory-efficient since it avoids adding duplicates to the queue.
• The method returns Boolean (the wrapper type) rather than boolean because the problem signature requires it. In practice, the autoboxing is negligible.

Complexity Analysis

Time Complexity: O(V + E)

Every airport (vertex) is dequeued and processed at most once thanks to the visited set. For each processed airport, we iterate over its outbound flights (edges). Across all airports, this sums to the total number of edges. Therefore the total work is O(V + E).

Space Complexity: O(V)

The visited set stores at most V airports. The queue also holds at most V airports in the worst case (imagine an airport with direct flights to every other airport). So the space usage is O(V).

BFS vs. DFS

Both BFS and DFS solve this reachability problem with identical time and space complexity. BFS uses a queue and explores level by level, while DFS uses a stack (or recursion) and dives deep before backtracking.

For a pure reachability check like this one, pick whichever feels more natural. BFS is nice because it naturally finds the shortest path (fewest layovers), while DFS can be more memory-efficient on narrow, deep graphs. In interviews, I'd recommend BFS for graph reachability since it's iterative and avoids stack overflow concerns on large graphs.

Common Pitfalls

1. Forgetting the visited set: Without it, the AUS-IAH cycle causes an infinite loop. Every graph traversal needs cycle protection.

2. Not handling missing keys: If an airport has no outbound flights, it won't appear as a key in the map. Using getOrDefault or checking for null prevents crashes.

3. Confusing directed vs. undirected: This graph is directed. Just because SFO flies to AUS doesn't mean AUS flies to SFO. Read the problem carefully to determine edge directionality.

4. Checking visited at the wrong time: If you only mark airports as visited when you dequeue them, you may enqueue the same airport multiple times. The algorithm still works correctly, but the queue can grow larger than necessary.

Interview Tips

When solving this problem in a 2026 interview:

1. Clarify the graph type: "Is this a directed or undirected graph?" This changes how you process edges.

2. State your approach clearly: "I'll use BFS with a visited set. The visited set prevents infinite loops from cycles, and BFS explores airports in order of connection distance."

3. Mention the alternative: "DFS would also work here with the same complexity. I'm choosing BFS because it naturally explores airports by number of hops."

4. Talk about edge cases:

   • Origin equals destination (should return true immediately)
   • Origin has no outbound flights
   • Destination is unreachable (disconnected component)

5. Discuss follow-ups the interviewer might ask:

   • "How would you find the actual route, not just whether one exists?" (Track parent pointers during BFS, then backtrack.)
   • "How would you find the shortest route?" (BFS already does this for unweighted graphs.)
   • "What about weighted edges, like flight costs?" (Use Dijkstra's algorithm.)

Key Takeaways

• Graph reachability is solved by BFS or DFS, both running in O(V + E) time and O(V) space. The visited set is non-negotiable for graphs with cycles.
• An adjacency list is the standard representation for sparse graphs. Each key maps to the list of nodes directly reachable from it.
• BFS explores neighbors level by level using a queue. It naturally finds the shortest path in unweighted graphs, making it a good default for reachability problems.
• Always handle missing keys in the adjacency list with getOrDefault or equivalent null checks to avoid runtime exceptions on nodes with no outbound edges.
• This problem is the foundation for harder graph algorithms. Once you're comfortable with BFS reachability, you're ready for cycle detection, topological sort, shortest paths, and connected components.

Related Problems

Once you are comfortable with basic graph reachability, push further with these:

• Number of Islands (grid-based graph traversal with DFS/BFS)
• Course Completion Feasibility (cycle detection with topological sort)
• Boggle Word Finder (DFS with backtracking on a grid graph)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. Whether this is your first graph problem or you're sharpening your skills before interview season, consistent practice on Firecode will get you there.

Solutions in Other Languages

Python

from collections import deque
from typing import List, Mapping


class Solution:
    def flight_check(self,
                     origin_destinations_map: Mapping[str, List[str]],
                     origin: str,
                     destination: str) -> bool:
        visited = set()
        queue = deque()
        queue.append(origin)

        while len(queue) > 0:
            airport_code = queue.popleft()

            if airport_code == destination:
                return True

            if airport_code not in visited:
                visited.add(airport_code)
                if airport_code in origin_destinations_map:
                    for dest in origin_destinations_map[airport_code]:
                        queue.append(dest)

        return False

JavaScript

class Solution {
  flightCheck(originDestinationsMap, origin, destination) {
    const visited = new Set();
    const queue = new Queue();
    queue.enqueue(origin);

    while (queue.nonEmpty()) {
      const airportCode = queue.dequeue();

      if (airportCode === destination) return true;

      if (!visited.has(airportCode)) {
        visited.add(airportCode);
        const destinations = originDestinationsMap.get(airportCode);
        if (destinations !== undefined)
          destinations.forEach(dest => queue.enqueue(dest));
      }
    }

    return false;
  }
}

TypeScript

class Solution {
  flightCheck(
    originDestinationsMap: Map<string, string[]>,
    origin: string,
    destination: string
  ): boolean {
    const visited = new Set<string>();
    const queue: string[] = [];
    queue.push(origin);

    while (queue.length > 0) {
      const airportCode = queue.shift()!;

      if (airportCode === destination) return true;

      if (!visited.has(airportCode)) {
        visited.add(airportCode);
        const destinations = originDestinationsMap.get(airportCode);
        if (destinations !== undefined)
          destinations.forEach(dest => queue.push(dest));
      }
    }

    return false;
  }
}

C++

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>

using namespace std;

class Solution {
public:
  bool flightCheck(
    map<string, vector<string>> originDestinationsMap,
    string origin,
    string destination
  ) {
    set<string> visited;
    queue<string> q;
    q.push(origin);

    while (!q.empty()) {
      string airportCode = q.front();
      q.pop();

      if (airportCode == destination) return true;

      if (visited.find(airportCode) == visited.end()) {
        visited.insert(airportCode);
        if (originDestinationsMap.find(airportCode)
            != originDestinationsMap.end()) {
          for (string dest : originDestinationsMap[airportCode]) {
            q.push(dest);
          }
        }
      }
    }

    return false;
  }
};

Go

package main

func (s *Solution) flightCheck(
	originDestinationsMap map[string][]string,
	origin string,
	destination string,
) bool {
	visited := make(map[string]bool)
	queue := []string{}
	queue = append(queue, origin)

	for len(queue) > 0 {
		airportCode := queue[0]
		queue = queue[1:]

		if airportCode == destination {
			return true
		}

		if !visited[airportCode] {
			visited[airportCode] = true
			if destinations, exists := originDestinationsMap[airportCode]; exists {
				queue = append(queue, destinations...)
			}
		}
	}

	return false
}

Scala

import scala.collection.mutable

class Solution {
  def flightCheck(
    originDestinationsMap: Map[String, List[String]],
    origin: String,
    destination: String
  ): Boolean = {
    val visited = mutable.Set[String]()
    val queue = mutable.Queue[String]()
    queue.enqueue(origin)

    while (queue.nonEmpty) {
      val airportCode = queue.dequeue

      if (airportCode == destination) return true

      if (!visited.contains(airportCode)) {
        visited.add(airportCode)
        originDestinationsMap.get(airportCode).foreach(queue.addAll(_))
      }
    }

    false
  }
}

Kotlin

class Solution {
  fun flightCheck(
    originDestinationsMap: Map<String, List<String>>,
    origin: String,
    destination: String
  ): Boolean {
    val visited = mutableSetOf<String>()
    val queue = ArrayDeque<String>()
    queue.add(origin)

    while (queue.isNotEmpty()) {
      val airportCode = queue.removeFirst()

      if (airportCode == destination) return true

      if (airportCode !in visited) {
        visited.add(airportCode)
        originDestinationsMap.getOrElse(airportCode) { emptyList() }
          .forEach { queue.add(it) }
      }
    }

    return false
  }
}

Ruby

require 'set'

class Solution
  def flight_check(origin_destinations_map, origin, destination)
    visited = Set.new
    queue = []
    queue.push(origin)

    while queue.any?
      airport_code = queue.shift

      return true if airport_code == destination

      unless visited.include?(airport_code)
        visited.add(airport_code)
        origin_destinations_map.fetch(airport_code, []).each do |dest|
          queue.push(dest)
        end
      end
    end

    false
  end
end

Swift

import Foundation

class Solution {
    func flightCheck(
        _ originDestinationsMap: [String: [String]],
        _ origin: String,
        _ destination: String
    ) -> Bool {
        var visited = Set<String>()
        var queue: [String] = []
        queue.append(origin)

        while !queue.isEmpty {
            let airportCode = queue.removeFirst()

            if airportCode == destination { return true }

            if !visited.contains(airportCode) {
                visited.insert(airportCode)
                for dest in originDestinationsMap[airportCode] ?? [] {
                    queue.append(dest)
                }
            }
        }

        return false
    }
}

C#

public class Solution {
    public bool FlightCheck(
        Dictionary<string, List<string>> originDestinationsMap,
        string origin,
        string destination
    ) {
        var visited = new HashSet<string>();
        var queue = new Queue<string>();
        queue.Enqueue(origin);

        while (queue.Count > 0) {
            var airportCode = queue.Dequeue();

            if (airportCode == destination) return true;

            if (!visited.Contains(airportCode)) {
                visited.Add(airportCode);
                if (originDestinationsMap.ContainsKey(airportCode)) {
                    originDestinationsMap[airportCode]
                        .ForEach(queue.Enqueue);
                }
            }
        }

        return false;
    }
}