Problem

Table: Flights

+-------------------+------+
| 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

Approach

We need to find the airport(s) with the highest total traffic, where traffic is the sum of all flights departing from or arriving at an airport. We can achieve this by summing flights_count for each airport as both a departure and arrival, then finding the maximum.

Code

MySQL
 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
)
Oracle
 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
  )
  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
    )
    GROUP BY airport_id
  )
)
PostgreSQL
 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) where N is the number of rows in Flights.
  • 🧺 Space complexity: O(M) where M is the number of unique airports.