Problem

Table: cities

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| state       | varchar |
| city        | varchar |
+-------------+---------+
(state, city) is the primary key (combination of columns with unique values) for this table.
Each row of this table contains the state name and the city name within that state.

Write a solution to find all the cities in each state and combine them into a single comma-separated string.

Return the result table ordered by state and city inascending order.

The result format is in the following example.

Example 1:

 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:
cities table:
+-------------+---------------+
| state       | city          |
+-------------+---------------+
| California  | Los Angeles   |
| California  | San Francisco |
| California  | San Diego     |
| Texas       | Houston       |
| Texas       | Austin        |
| Texas       | Dallas        |
| New York    | New York City |
| New York    | Buffalo       |
| New York    | Rochester     |
+-------------+---------------+
Output:
+-------------+---------------------------------------+
| state       | cities                                |
+-------------+---------------------------------------+
| California  | Los Angeles, San Diego, San Francisco |
| New York    | Buffalo, New York City, Rochester     |
| Texas       | Austin, Dallas, Houston               |
+-------------+---------------------------------------+
Explanation:
* **California:** All cities ("Los Angeles", "San Diego", "San Francisco") are listed in a comma-separated string.
* **New York:** All cities ("Buffalo", "New York City", "Rochester") are listed in a comma-separated string.
* **Texas:** All cities ("Austin", "Dallas", "Houston") are listed in a comma-separated string.
**Note:** The output table is ordered by the state name in ascending order.

Solution

Method 1 – String Aggregation with GROUP_CONCAT / STRING_AGG

Intuition

To list all cities in each state as a single comma-separated string, we need to group the cities by state and concatenate the city names in sorted order.

Approach

  • For MySQL:
    1. Use GROUP_CONCAT to aggregate city names for each state.
    2. Use ORDER BY inside GROUP_CONCAT to sort city names.
    3. Group by state and order the result by state.
  • For PostgreSQL:
    1. Use STRING_AGG to concatenate city names for each state.
    2. Use ORDER BY within STRING_AGG for city sorting.
    3. Group by state and order the result by state.
  • For Python (Pandas):
    1. Group the DataFrame by state.
    2. Sort city names within each group and join them with commas.
    3. Sort the final DataFrame by state.

Code

1
2
3
4

SELECT state, GROUP_CONCAT(city ORDER BY city) AS cities
FROM cities
GROUP BY state
ORDER BY state;
1
2
3
4

SELECT state, STRING_AGG(city, ',' ORDER BY city) AS cities
FROM cities
GROUP BY state
ORDER BY state;
1
2
3
4
5
6
7

class Solution:
    def find_cities_in_each_state(self, df):
        ans = df.sort_values(['state', 'city']) \
                .groupby('state')['city'] \
                .apply(lambda x: ','.join(x)) \
                .reset_index(name='cities')
        return ans.sort_values('state').reset_index(drop=True)

Complexity

  • ⏰ Time complexity: O(n log n), due to sorting cities within each state.
  • 🧺 Space complexity: O(n), for storing the grouped and concatenated results.