LeetCode 2112 - The Airport With the Most Traffic

LeetCode Problem 2112

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to find the airport(s) with the most traffic using a table of flights. Each row of the Flights table represents a direct connection from departure_airport to arrival_airport along with the number of flights flights_count for that route. The traffic for an airport is defined as the total number of flights departing from or arriving at that airport. If multiple airports tie for the highest traffic, we must return all of them in any order.

The input is a relational table with three columns: departure_airport, arrival_airport, and flights_count. The output is a table with a single column airport_id that contains the airport(s) with the maximum traffic. The constraints imply that the table is non-empty and (departure_airport, arrival_airport) pairs are unique, so we can safely sum the flights_count grouped by each airport. Edge cases include multiple airports tying for the maximum traffic or airports appearing only as departures or arrivals.

Approaches

The brute-force approach would be to iterate over all airports in the dataset, calculate the sum of flights departing and arriving for each airport individually, and then pick the maximum. This would require multiple scans of the table, which is inefficient for large datasets.

The optimal approach leverages a single pass aggregation. We can scan through the Flights table once, incrementally updating a traffic counter for both the departure and arrival airports. After this aggregation, we can find the maximum traffic and select all airports with that value. This method avoids multiple scans and makes the solution simple and efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(n)	For each airport, sum arrivals and departures separately. Multiple table scans.
Optimal	O(n)	O(n)	Single pass aggregation using a hash map or SQL GROUP BY with SUM.

Algorithm Walkthrough

1. Initialize a map or temporary table to store the total traffic for each airport.
2. Iterate over every row in the Flights table. For each row, extract departure_airport, arrival_airport, and flights_count.
3. For the departure_airport, add flights_count to its total traffic in the map. Do the same for the arrival_airport.
4. After processing all rows, determine the maximum traffic value across all airports in the map.
5. Select all airports whose traffic equals the maximum value and return them as the result.

Why it works: The approach guarantees correctness because each flight contributes exactly once to the departure airport's traffic and once to the arrival airport's traffic. Summing these in a single pass ensures that no airport is missed and avoids redundant computation.

Python Solution

import pandas as pd

# For LeetCode SQL, we would use a query; for Python simulation:

def mostTrafficAirports(flights: pd.DataFrame) -> pd.DataFrame:
    traffic = {}
    for _, row in flights.iterrows():
        dep, arr, count = row['departure_airport'], row['arrival_airport'], row['flights_count']
        traffic[dep] = traffic.get(dep, 0) + count
        traffic[arr] = traffic.get(arr, 0) + count
    
    max_traffic = max(traffic.values())
    result = pd.DataFrame({'airport_id': [airport for airport, t in traffic.items() if t == max_traffic]})
    return result

The code uses a dictionary to accumulate traffic counts. Each row contributes to both departure and arrival counts. After processing all rows, we determine the maximum value and extract all airports that match it.

Go Solution

package main

type Flight struct {
	DepartureAirport int
	ArrivalAirport   int
	FlightsCount     int
}

func mostTrafficAirports(flights []Flight) []int {
	traffic := make(map[int]int)
	for _, f := range flights {
		traffic[f.DepartureAirport] += f.FlightsCount
		traffic[f.ArrivalAirport] += f.FlightsCount
	}
	
	maxTraffic := 0
	for _, t := range traffic {
		if t > maxTraffic {
			maxTraffic = t
		}
	}
	
	var result []int
	for airport, t := range traffic {
		if t == maxTraffic {
			result = append(result, airport)
		}
	}
	return result
}

In Go, we use a map to accumulate traffic counts. We iterate once to calculate totals and then iterate over the map to identify airports with maximum traffic.

Worked Examples

Example 1 Table:

Airport	Traffic Calculation	Total
1	departures 4 + arrivals 5	9
2	departures 10 + arrivals 4	14
4	arrivals 5	5

Maximum is 14, so airport 2 is returned.

Example 2 Table:

Airport	Traffic Calculation	Total
1	4 + 5	9
2	5 + 4	9
3	5 + 4	9
4	4 + 5	9
5	7	7
6	7	7

Maximum is 9, so airports 1, 2, 3, 4 are returned.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass over all flights to calculate traffic, plus one pass over map for max.
Space	O(n)	Storage for traffic counts per airport.

The reasoning is that each flight is processed exactly once and each airport is stored once in the map.

Test Cases

import pandas as pd

# Test case 1
flights = pd.DataFrame({
    'departure_airport': [1,2,2],
    'arrival_airport': [2,1,4],
    'flights_count': [4,5,5]
})
assert set(mostTrafficAirports(flights)['airport_id']) == {2}  # max traffic = 14

# Test case 2
flights = pd.DataFrame({
    'departure_airport': [1,2,3,4,5],
    'arrival_airport': [2,1,4,3,6],
    'flights_count': [4,5,5,4,7]
})
assert set(mostTrafficAirports(flights)['airport_id']) == {1,2,3,4}  # max traffic = 9

# Test case 3 (single airport)
flights = pd.DataFrame({
    'departure_airport': [1],
    'arrival_airport': [2],
    'flights_count': [10]
})
assert set(mostTrafficAirports(flights)['airport_id']) == {1,2}  # both airports tied

Test	Why
Example 1	Validates correct summing of departures and arrivals
Example 2	Validates handling multiple airports tied for max traffic
Single flight	Validates edge case with minimum input size

Edge Cases

1. Single Flight: When there is only one flight, both airports connected by it should be considered as having maximum traffic. The algorithm correctly adds the flight count to both departure and arrival.
2. Tied Airports: If multiple airports have the same maximum traffic, the solution must include all of them. Using a final filter with traffic == max_traffic ensures this.
3. Airport Appears Only Once: Some airports might appear only as a departure or only as an arrival. The algorithm handles this naturally because it initializes counts to zero using get or += in maps.

This solution is comprehensive, handles all edge cases, and provides a clean O(n) aggregation-based computation.