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 in ascending order.
The result format is in the following example.
Example:
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:
Note: The output table is ordered by the state name in ascending order.
Problem Overview: You are given a table of cities where each row contains a city name and the state it belongs to. The goal is to return one row per state and list all cities within that state together in a single aggregated result.
Approach 1: SQL Grouping and Aggregation (O(n) time, O(n) space)
The direct solution uses SQL aggregation with GROUP BY. Iterate through all rows and group records by the state column. For each group, aggregate the city names using an aggregation function such as GROUP_CONCAT in MySQL. This collects all city values from the same state into one combined output. If the problem requires sorted output, apply ORDER BY city inside the aggregation. The database engine handles grouping internally using hashing or sorting, giving overall O(n) time with O(n) space for the grouped result.
This approach is standard for database interview questions that require summarizing rows. Instead of manually scanning multiple times, you rely on SQL’s built‑in aggregation pipeline to compute the result efficiently.
Approach 2: Pandas GroupBy Aggregation (O(n) time, O(n) space)
In Pandas, the same idea is implemented using groupby(). First group the DataFrame by the state column. Then aggregate the city column using a join operation that merges all city names belonging to the same group. If ordering is required, sort the city values inside the aggregation before joining them. The groupby operation internally partitions rows by key and processes each group once, resulting in O(n) time and O(n) space.
This pattern appears frequently in Pandas data processing tasks and mirrors SQL aggregation semantics. It is essentially the DataFrame equivalent of GROUP BY combined with string aggregation.
Recommended for interviews: The grouping and aggregation approach is exactly what interviewers expect for database problems like this. Demonstrating the GROUP BY pattern shows you understand relational aggregation. For Python data analysis variants, using groupby in Pandas demonstrates familiarity with SQL-style aggregation workflows applied to tabular datasets.
We can first group by the state field, then sort the city field within each group, and finally use the GROUP_CONCAT function to concatenate the sorted city names into a comma-separated string.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| SQL GROUP BY with Aggregation | O(n) | O(n) | Standard database queries where rows must be grouped and summarized per key |
| Pandas groupby() Aggregation | O(n) | O(n) | Data analysis workflows using Python DataFrames instead of SQL |
Leetcode 3198 - Find Cities in Each State GROUP_CONCAT() Explained - Solved by Everyday Data Science • Everyday Data Science • 661 views views
Watch 2 more video solutions →Practice Find Cities in Each State with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor