Firecode logo
Sign In Start Free Trial

Intro to graphs: Generate a non-stop flight service adjacency list

AS
Ackshaey Singh
Difficulty Hard
Time Complexity
O(n)
Space Complexity
O(n)
Graph Set Map
Firecode

You're sitting in a technical phone screen and the interviewer says, "Let's say you're building a flight booking system. We have a list of non-stop routes between airports. How would you organize this data so you can quickly look up all destinations from a given airport?" Before you even think about shortest paths or Dijkstra's algorithm, you need to solve a more fundamental problem: how do you represent a graph in code? This question tests exactly that, and it's one of the most practical introductions to graph data structures you'll encounter.

TL;DR

Given a list of [origin, destination] flight pairs, build a HashMap where each origin airport maps to a list of distinct destination airports reachable by non-stop flights. Use a Map<String, Set<String>> to collect destinations (the Set handles duplicates automatically), then convert each Set to a List before returning. This runs in O(n) time and O(n) space.

Why This Problem Matters

Graphs are everywhere in software engineering. Social networks, maps, dependency trees, recommendation engines - they all rely on graph representations. The adjacency list is the most common way to represent sparse graphs in practice because it's memory-efficient and allows fast neighbor lookups. If you've never built one from scratch, this problem is a perfect starting point. It strips away the algorithmic complexity of graph traversal and focuses on the core skill: organizing relational data into a graph structure.

Graphs and Adjacency Lists: A Quick Primer

A graph is a collection of nodes (vertices) connected by edges. In our case, airports are nodes and non-stop flights are directed edges. A directed edge from SFO to AUS means there's a flight from SFO to AUS, but not necessarily one going back.

An adjacency list represents a graph as a map where each key is a node and its value is a list of neighbors. For directed graphs, the neighbors are the nodes you can reach directly from that key.

Here's what our flight network looks like for the input [["SFO","AUS"], ["SFO","MIA"], ["JFK","MIA"]]:

Loading visualization...

The adjacency list for this graph would be:

SFO -> [AUS, MIA]
JFK -> [MIA]

Each origin airport maps to the set of airports you can fly to directly.

Understanding the Problem

Given: A list of [origin, destination] string pairs representing non-stop flights Return: A Map<String, List<String>> where each origin maps to a list of distinct destinations Constraints: 1 ≤ distinct airports ≤ 20, 1 ≤ n ≤ 50

Edge Cases to Consider

  1. Duplicate flights: [["SFO","AUS"], ["SFO","AUS"]] should produce SFO -> [AUS], not SFO -> [AUS, AUS]
  2. Empty input: An empty list should return an empty map
  3. Single flight: [["SFO","AUS"]] produces SFO -> [AUS]
  4. Multiple origins: Each origin airport gets its own entry in the map

The duplicate handling is the subtle part. The problem says "distinct" destinations, so we need a data structure that filters duplicates for us.

Solution Approach

Let's think about this step by step.

We need to group destinations by origin. A HashMap is perfect for this since we get O(1) lookups by origin. But we also need to handle duplicates. If we use a List as the value, we'd have to check for existence before adding each destination, which is O(k) per check where k is the current number of destinations. A Set gives us O(1) deduplication for free.

The strategy is straightforward:

  1. Create a Map<String, Set<String>> to accumulate unique destinations per origin
  2. Iterate through each flight pair, adding the destination to the appropriate origin's Set
  3. Convert each Set to a List before returning

Let's trace through the example input [["SFO","AUS"], ["SFO","MIA"], ["SFO","AUS"], ["JFK","MIA"]]:

Loading visualization...

Notice how the third pair ["SFO","AUS"] is silently absorbed by the Set. No conditional checks needed.

Implementation

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

import java.util.*;

public class Solution {
  public Map<String, List<String>> graphAdjacencyList(
    List<List<String>> originDestinations
  ) {
    // Build the graph using Sets to handle duplicate destinations
    Map<String, Set<String>> adjacencySet = new HashMap<>();

    for (List<String> pair : originDestinations) {
      String origin = pair.get(0);
      String destination = pair.get(1);

      adjacencySet.putIfAbsent(origin, new HashSet<>());
      adjacencySet.get(origin).add(destination);
    }

    // Convert Sets to Lists for the return type
    Map<String, List<String>> result = new HashMap<>();
    for (Map.Entry<String, Set<String>> entry : adjacencySet.entrySet()) {
      result.put(entry.getKey(), new ArrayList<>(entry.getValue()));
    }

    return result;
  }
}

Let's walk through the key decisions:

  • putIfAbsent initializes a new HashSet for an origin only if one doesn't already exist. This avoids a NullPointerException when calling add() on the Set.
  • HashSet.add() returns false if the element already exists, but we don't even need to check - the Set just silently handles duplicates.
  • The final conversion loop wraps each Set in an ArrayList, which is a simple O(k) operation per origin.

Handling the Larger Test Case

Here's a more complex flight network with bidirectional routes and multiple hubs:

Loading visualization...

For the input [["SFO","AUS"], ["IAH","AUS"], ["JFK","TPA"], ["AUS","IAH"], ["SFO","JFK"], ["SFO","AUS"], ["JFK","MIA"]], our algorithm produces:

SFO -> [AUS, JFK]
IAH -> [AUS]
JFK -> [TPA, MIA]
AUS -> [IAH]

Notice that AUS -> IAH and IAH -> AUS are separate entries because this is a directed graph. A flight from AUS to IAH doesn't imply a return flight.

Complexity Analysis

Time Complexity: O(n)

We iterate through each of the n flight pairs exactly once. For each pair:

  • HashMap lookup/insert: O(1) amortized
  • HashSet add: O(1) amortized
  • The final conversion loop visits each destination once across all origins, which is at most n total insertions

Total: O(n).

Space Complexity: O(n)

In the worst case, every flight pair involves a unique origin and destination. The HashMap and Sets together store at most n entries (one per flight pair), and the result map stores the same data in List form.

Total: O(n) additional space.

Why Not Just Use Lists?

You could skip the Set intermediary and use List<String> directly, checking contains() before each add. That would work but degrades the per-insertion cost to O(k) where k is the number of destinations for that origin. With Sets, insertion remains O(1) amortized regardless of how many destinations an origin has.

Common Pitfalls

  1. Forgetting to handle duplicates: Using a List without deduplication will include duplicate destinations
  2. NullPointerException on first insert: If you don't initialize the Set/List for a new origin before calling .add(), you'll get a null pointer
  3. Treating the graph as undirected: A flight from SFO to AUS doesn't mean there's a flight from AUS to SFO. Only add the pair in the direction given.
  4. Returning the intermediate Set map: The problem asks for Map<String, List<String>>, not Map<String, Set<String>>

Interview Tips

  1. Start by clarifying: "Is this a directed or undirected graph?" (Directed, since flights are one-way.) "Should I handle duplicate pairs?" (Yes, destinations must be distinct.)
  2. Mention the data structure choice: Explain why you're using a Set as the intermediate value type. This shows you're thinking about correctness and efficiency simultaneously.
  3. Draw the graph: Sketch the flight network on the whiteboard. It makes the adjacency list structure immediately obvious.
  4. Discuss alternatives: Mention that adjacency matrices work better for dense graphs, while adjacency lists (what we're building) are more space-efficient for sparse graphs like flight networks.

Real-World Applications

This exact pattern shows up constantly in production codebases:

  • Social networks: User ID to list of friends/followers
  • Package managers: Package name to list of dependencies
  • Route planning: Airport/station to list of reachable destinations
  • Course prerequisites: Course ID to list of required courses
  • Web crawlers: URL to list of linked URLs

If you've ever used a HashMap to group items by a key, you've essentially built an adjacency list.

Solutions in Other Languages

Python

from typing import List, Mapping


class Solution:
    def graph_adjacency_list(self,
                             origin_destinations: List[List[str]]
                             ) -> Mapping[str, List[str]]:
        adjacency_set = {}

        for pair in origin_destinations:
            origin = pair[0]
            destination = pair[1]

            if origin not in adjacency_set:
                adjacency_set[origin] = set()
            adjacency_set[origin].add(destination)

        return {origin: list(destinations)
                for origin, destinations in adjacency_set.items()}

JavaScript

class Solution {
  graphAdjacencyList(originDestinations) {
    const adjacencySet = new Map();

    originDestinations.forEach(pair => {
      const origin = pair[0];
      const destination = pair[1];

      if (!adjacencySet.has(origin)) {
        adjacencySet.set(origin, new Set());
      }
      adjacencySet.get(origin).add(destination);
    });

    return new Map(
      [...adjacencySet.entries()].map(([origin, destinations]) =>
        [origin, Array.from(destinations)]
      )
    );
  }
}

TypeScript

class Solution {
  graphAdjacencyList(originDestinations: string[][]): Map<string, string[]> {
    const adjacencySet = new Map<string, Set<string>>();

    originDestinations.forEach(pair => {
      const origin = pair[0];
      const destination = pair[1];

      if (!adjacencySet.has(origin)) {
        adjacencySet.set(origin, new Set<string>());
      }
      adjacencySet.get(origin)!.add(destination);
    });

    return new Map(
      [...adjacencySet.entries()].map(([origin, destinations]) =>
        [origin, Array.from(destinations)]
      )
    );
  }
}

C++

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

using namespace std;

class Solution {
public:
  map<string, vector<string>> graphAdjacencyList(
    vector<vector<string>> originDestinations
  ) {
    map<string, set<string>> adjacencySet;

    for (const auto& pair : originDestinations) {
      string origin = pair[0];
      string destination = pair[1];
      adjacencySet[origin].insert(destination);
    }

    map<string, vector<string>> result;
    for (auto& entry : adjacencySet) {
      result[entry.first] = vector<string>(entry.second.begin(), entry.second.end());
    }

    return result;
  }
};

Go

package main

import "sort"

func GraphAdjacencyList(originDestinations [][]string) map[string][]string {
    adjacencySet := make(map[string]map[string]bool)

    for _, pair := range originDestinations {
        origin := pair[0]
        destination := pair[1]

        if adjacencySet[origin] == nil {
            adjacencySet[origin] = make(map[string]bool)
        }
        adjacencySet[origin][destination] = true
    }

    result := make(map[string][]string)
    for origin, destSet := range adjacencySet {
        destinations := make([]string, 0, len(destSet))
        for dest := range destSet {
            destinations = append(destinations, dest)
        }
        sort.Strings(destinations)
        result[origin] = destinations
    }

    return result
}

Go doesn't have a built-in Set type, so we use map[string]bool as a stand-in. The sort.Strings call ensures deterministic output ordering.

Scala

class Solution {
  def graphAdjacencyList(
    originDestinations: List[List[String]]
  ): Map[String, List[String]] = {
    originDestinations
      .groupBy(_.head)
      .map {
        case (origin, pairs) =>
          origin -> pairs.map(_.last).distinct
      }
  }
}

Scala's functional style makes this particularly concise. groupBy handles the map creation, and distinct removes duplicates.

Kotlin

class Solution {
  fun graphAdjacencyList(
    originDestinations: List<List<String>>
  ): Map<String, List<String>> {
    val adjacencySet = mutableMapOf<String, MutableSet<String>>()

    for (pair in originDestinations) {
      val origin = pair[0]
      val destination = pair[1]
      adjacencySet.getOrPut(origin) { mutableSetOf() }.add(destination)
    }

    return adjacencySet.mapValues { it.value.toList() }
  }
}

Swift

func graphAdjacencyList(_ originDestinations: [[String]]) -> [String: [String]] {
    var adjacencySet = [String: Set<String>]()

    for pair in originDestinations {
        let origin = pair[0]
        let destination = pair[1]

        if adjacencySet[origin] == nil {
            adjacencySet[origin] = Set<String>()
        }
        adjacencySet[origin]!.insert(destination)
    }

    return adjacencySet.mapValues { Array($0) }
}

Ruby

require 'set'

class Solution
  def graph_adjacency_list(origin_destinations)
    adjacency_set = Hash.new { |h, k| h[k] = Set.new }

    origin_destinations.each do |pair|
      origin = pair[0]
      destination = pair[1]
      adjacency_set[origin].add(destination)
    end

    adjacency_set.transform_values(&:to_a)
  end
end

Ruby's Hash.new with a block default makes this clean - any new key automatically gets a fresh Set.

Rust

use std::collections::{HashMap, HashSet};

impl Solution {
    pub fn graph_adjacency_list(
        &self, origin_destinations: Vec<Vec<String>>
    ) -> HashMap<String, Vec<String>> {
        let mut adjacency_set: HashMap<String, HashSet<String>> = HashMap::new();

        for pair in &origin_destinations {
            let origin = &pair[0];
            let destination = &pair[1];
            adjacency_set
                .entry(origin.clone())
                .or_insert_with(HashSet::new)
                .insert(destination.clone());
        }

        let mut result: HashMap<String, Vec<String>> = HashMap::new();
        for (key, value_set) in adjacency_set {
            result.insert(key, value_set.into_iter().collect());
        }

        result
    }
}

Dart

Map<String, List<String>> graphAdjacencyList(
  List<List<String>> originDestinations
) {
  Map<String, Set<String>> adjacencySet = {};

  for (List<String> pair in originDestinations) {
    String origin = pair[0];
    String destination = pair[1];

    adjacencySet.putIfAbsent(origin, () => {});
    adjacencySet[origin]!.add(destination);
  }

  return adjacencySet.map(
    (key, value) => MapEntry(key, value.toList())
  );
}

PHP

class Solution {
    public function graphAdjacencyList(array $originDestinations): array {
        $adjacencySet = [];

        foreach ($originDestinations as $pair) {
            $origin = $pair[0];
            $destination = $pair[1];

            if (!isset($adjacencySet[$origin])) {
                $adjacencySet[$origin] = [];
            }
            $adjacencySet[$origin][$destination] = true;
        }

        $result = [];
        foreach ($adjacencySet as $origin => $destinations) {
            $result[$origin] = array_keys($destinations);
        }

        return $result;
    }
}

C#

public class Solution {
    public Dictionary<string, List<string>> GraphAdjacencyList(
        List<List<string>> originDestinations
    ) {
        var adjacencySet = new Dictionary<string, HashSet<string>>();

        foreach (var pair in originDestinations) {
            var origin = pair[0];
            var destination = pair[1];

            if (!adjacencySet.ContainsKey(origin)) {
                adjacencySet[origin] = new HashSet<string>();
            }
            adjacencySet[origin].Add(destination);
        }

        var result = new Dictionary<string, List<string>>();
        foreach (var entry in adjacencySet) {
            result[entry.Key] = new List<string>(entry.Value);
        }

        return result;
    }
}

Practice Makes Perfect

Building an adjacency list is the foundation for almost every graph algorithm. Once you're comfortable with this representation, you're ready to tackle problems that actually traverse the graph:

  • Number of Islands (graph traversal with DFS/BFS)
  • Course Completion Feasibility (topological sort on a directed graph)
  • Boggle Word Finder (graph search with backtracking)

These problems all start by building exactly the kind of adjacency list we just implemented. The only difference is what you do with it afterward.

If you want to practice this problem interactively with hints that guide you through the solution step by step, check it out on Firecode.io. With over 50,000 engineers who've used the platform to prepare for technical interviews, it's built to help you internalize these patterns through spaced repetition so they stick when it counts.