Skip to main content
Talentd

Find Cities in Each State - Solution & Explanation

EasyPremiumFree on FleetCodeDatabase4 min read
Practice this problem

Problem Statement

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:

  • 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.

Approach Overview

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.

Solution

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.

Code

MySQLPandas

MySQL

Pandas

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
SQL GROUP BY with AggregationO(n)O(n)Standard database queries where rows must be grouped and summarized per key
Pandas groupby() AggregationO(n)O(n)Data analysis workflows using Python DataFrames instead of SQL

Video Solution

Leetcode 3198 - Find Cities in Each State GROUP_CONCAT() Explained - Solved by Everyday Data Science • Everyday Data Science • 712 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Find Cities in Each State easy or hard?
Find Cities in Each State is considered an Easy database problem. It mainly tests familiarity with GROUP BY aggregation and basic SQL data summarization rather than complex algorithms.
Find Cities in Each State Python/Java solution
In SQL (commonly used with Java backends), use GROUP BY with GROUP_CONCAT to aggregate city names. In Python data workflows, use Pandas groupby('state') and aggregate the city column by joining values into a single string per group.
How to solve Find Cities in Each State in O(n)?
Use a GROUP BY query on the state column and aggregate the city column using a function such as GROUP_CONCAT. The database engine builds groups while scanning rows once, making the overall complexity O(n). Pandas achieves the same complexity using groupby() and aggregation.
What is the best approach for Find Cities in Each State?
The most efficient approach uses SQL aggregation with GROUP BY. Group rows by the state column and aggregate city names using functions like GROUP_CONCAT in MySQL. This processes the table in O(n) time and produces one row per state with all cities combined.
Is Find Cities in Each State asked at Google/Amazon/Meta?
Database aggregation questions like this appear frequently in SQL interview rounds at companies such as Amazon, Meta, and Google. Candidates are expected to understand GROUP BY, aggregation functions, and how relational databases summarize grouped data.
What data structure is used in Find Cities in Each State?
Conceptually the solution relies on grouping by a key, which behaves like a hash map from state to a list of cities. SQL databases implement this internally using hashing or sorting during GROUP BY execution.
What is the time complexity of Find Cities in Each State?
The grouping and aggregation solution runs in O(n) time where n is the number of rows in the table. The database scans the table once and groups rows by state. Space complexity is O(n) for storing grouped results.

Ready to solve this problem?

Practice Find Cities in Each State with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary