Problem

Table: Flights

1
2
3
4
5
6
7
8
9

+-------------------+------+
| Column Name       | Type |
+-------------------+------+
| departure_airport | int  |
| arrival_airport   | int  |
| flights_count     | int  |
+-------------------+------+
(departure_airport, arrival_airport) is the primary key column (combination of columns with unique values) for this table.
Each row of this table indicates that there were flights_count flights that departed from departure_airport and arrived at arrival_airport.

Write a solution to report the ID of the airport with the most traffic. The airport with the most traffic is the airport that has the largest total number of flights that either departed from or arrived at the airport. If there is more than one airport with the most traffic, report them all.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

Input: 
Flights table:
+-------------------+-----------------+---------------+
| departure_airport | arrival_airport | flights_count |
+-------------------+-----------------+---------------+
| 1                 | 2               | 4             |
| 2                 | 1               | 5             |
| 2                 | 4               | 5             |
+-------------------+-----------------+---------------+
Output: 
+------------+
| airport_id |
+------------+
| 2          |
+------------+
Explanation: 
Airport 1 was engaged with 9 flights (4 departures, 5 arrivals).
Airport 2 was engaged with 14 flights (10 departures, 4 arrivals).
Airport 4 was engaged with 5 flights (5 arrivals).
The airport with the most traffic is airport 2.

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Input: 
Flights table:
+-------------------+-----------------+---------------+
| departure_airport | arrival_airport | flights_count |
+-------------------+-----------------+---------------+
| 1                 | 2               | 4             |
| 2                 | 1               | 5             |
| 3                 | 4               | 5             |
| 4                 | 3               | 4             |
| 5                 | 6               | 7             |
+-------------------+-----------------+---------------+
Output: 
+------------+
| airport_id |
+------------+
| 1          |
| 2          |
| 3          |
| 4          |
+------------+
Explanation: 
Airport 1 was engaged with 9 flights (4 departures, 5 arrivals).
Airport 2 was engaged with 9 flights (5 departures, 4 arrivals).
Airport 3 was engaged with 9 flights (5 departures, 4 arrivals).
Airport 4 was engaged with 9 flights (4 departures, 5 arrivals).
Airport 5 was engaged with 7 flights (7 departures).
Airport 6 was engaged with 7 flights (7 arrivals).
The airports with the most traffic are airports 1, 2, 3, and 4.

Solution

Method 1 - Aggregate Airport Traffic

Intuition

Total traffic for an airport equals the sum of flights that departed from it plus the flights that arrived to it. We can compute per-airport totals by summing flights_count twice: once treating departure_airport as airport_id and once treating arrival_airport as airport_id, then grouping by airport_id.

Approach

  1. Use a UNION ALL over the Flights table to produce rows (airport_id, flights_count) for both departures and arrivals.
  2. Group by airport_id and compute total_traffic = SUM(flights_count).
  3. Find the maximum total_traffic and return all airport_ids whose total_traffic equals this maximum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

SELECT airport_id
FROM (
  SELECT airport_id, SUM(flights_count) AS total_traffic
  FROM (
    SELECT departure_airport AS airport_id, flights_count FROM Flights
    UNION ALL
    SELECT arrival_airport AS airport_id, flights_count FROM Flights
  ) t
  GROUP BY airport_id
) s
WHERE total_traffic = (
  SELECT MAX(total_traffic) FROM (
    SELECT airport_id, SUM(flights_count) AS total_traffic
    FROM (
      SELECT departure_airport AS airport_id, flights_count FROM Flights
      UNION ALL
      SELECT arrival_airport AS airport_id, flights_count FROM Flights
    ) t
    GROUP BY airport_id
  ) x
);
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

SELECT airport_id
FROM (
  SELECT airport_id, SUM(flights_count) AS total_traffic
  FROM (
    SELECT departure_airport AS airport_id, flights_count FROM Flights
    UNION ALL
    SELECT arrival_airport AS airport_id, flights_count FROM Flights
  ) t
  GROUP BY airport_id
)
WHERE total_traffic = (
  SELECT MAX(total_traffic) FROM (
    SELECT airport_id, SUM(flights_count) AS total_traffic
    FROM (
      SELECT departure_airport AS airport_id, flights_count FROM Flights
      UNION ALL
      SELECT arrival_airport AS airport_id, flights_count FROM Flights
    ) t
    GROUP BY airport_id
  ) x
);
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

WITH airport_traffic AS (
  SELECT airport_id, SUM(flights_count) AS total_traffic
  FROM (
    SELECT departure_airport AS airport_id, flights_count FROM Flights
    UNION ALL
    SELECT arrival_airport AS airport_id, flights_count FROM Flights
  ) t
  GROUP BY airport_id
)
SELECT airport_id
FROM airport_traffic
WHERE total_traffic = (SELECT MAX(total_traffic) FROM airport_traffic);

Complexity

  • ⏰ Time complexity: O(N) – We scan the Flights table a constant number of times and perform grouping/aggregation over the resulting rows (N = number of flight records).
  • 🧺 Space complexity: O(M) – We store aggregated traffic per airport (M = number of distinct airports).