Skip to main content
Talentd

Find Cities in Each State II - Solution & Explanation

MediumPremiumFree on FleetCodeDatabase5 min read
Practice this problem

Problem Statement

Table: cities

+-------------+---------+
| Column Name | Type    | 
+-------------+---------+
| state       | varchar |
| city        | varchar |
+-------------+---------+
(state, city) is the 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 analyze them based on the following requirements:

  • Combine all cities into a comma-separated string for each state.
  • Only include states that have at least 3 cities.
  • Only include states where at least one city starts with the same letter as the state name.

Return the result table ordered by the count of matching-letter cities in descending order and then by state name in ascending order.

The result format is in the following example.

 

Example:

Input:

cities table:

+--------------+---------------+
| state        | city          |
+--------------+---------------+
| New York     | New York City |
| New York     | Newark        |
| New York     | Buffalo       |
| New York     | Rochester     |
| California   | San Francisco |
| California   | Sacramento    |
| California   | San Diego     |
| California   | Los Angeles   |
| Texas        | Tyler         |
| Texas        | Temple        |
| Texas        | Taylor        |
| Texas        | Dallas        |
| Pennsylvania | Philadelphia  |
| Pennsylvania | Pittsburgh    |
| Pennsylvania | Pottstown     |
+--------------+---------------+

Output:

+-------------+-------------------------------------------+-----------------------+
| state       | cities                                    | matching_letter_count |
+-------------+-------------------------------------------+-----------------------+
| Pennsylvania| Philadelphia, Pittsburgh, Pottstown       | 3                     |
| Texas       | Dallas, Taylor, Temple, Tyler             | 3                     |
| New York    | Buffalo, Newark, New York City, Rochester | 2                     |
+-------------+-------------------------------------------+-----------------------+

Explanation:

  • Pennsylvania:
    • Has 3 cities (meets minimum requirement)
    • All 3 cities start with 'P' (same as state)
    • matching_letter_count = 3
  • Texas:
    • Has 4 cities (meets minimum requirement)
    • 3 cities (Taylor, Temple, Tyler) start with 'T' (same as state)
    • matching_letter_count = 3
  • New York:
    • Has 4 cities (meets minimum requirement)
    • 2 cities (Newark, New York City) start with 'N' (same as state)
    • matching_letter_count = 2
  • California is not included in the output because:
    • Although it has 4 cities (meets minimum requirement)
    • No cities start with 'C' (doesn't meet the matching letter requirement)

Note:

  • Results are ordered by matching_letter_count in descending order
  • When matching_letter_count is the same (Texas and New York both have 2), they are ordered by state name alphabetically
  • Cities in each row are ordered alphabetically

Approach Overview

Problem Overview: You need to group cities by their state and return only the states that satisfy a specific condition based on their cities. The task is fundamentally a database aggregation problem: collect rows per state, compute a metric such as count or list of cities, and filter the groups that meet the requirement.

Approach 1: GROUP BY + HAVING Aggregation (O(n) time, O(k) space)

The most direct SQL solution groups rows using GROUP BY state. Aggregation functions such as COUNT(), GROUP_CONCAT(), or similar operations summarize the cities belonging to each state. After grouping, apply a filter using HAVING to keep only states that meet the required condition (for example, a minimum number of cities). This works because HAVING filters aggregated groups after the grouping phase, unlike WHERE which filters individual rows.

In practice the query scans the table once, builds grouped aggregates, and discards groups that fail the condition. The time complexity is O(n) where n is the number of rows in the cities table. Space complexity is O(k) where k is the number of distinct states being tracked during aggregation. This pattern appears frequently in SQL and database interview problems.

Approach 2: Window Function + Filtering (O(n) time, O(n) space)

Another option uses window functions. Compute a per‑state metric with a window expression such as COUNT(*) OVER (PARTITION BY state). This attaches the state-level statistic to every row while preserving the original table structure. After computing the window value, filter rows using the required condition (for example, keeping rows where the state count passes the threshold).

This approach is useful when you still need row-level data after computing group statistics. Instead of collapsing rows like GROUP BY, window functions keep the detailed records. The database still scans the dataset once, so time complexity remains O(n), though intermediate storage can reach O(n) depending on the engine. Window functions are common in analytical SQL workflows and problems involving ranking, partitions, or per-group metrics.

Approach 3: Pandas groupby + filter (O(n) time, O(k) space)

In a Pandas environment, the same logic translates directly using groupby(). First group the dataframe by the state column. Then apply aggregation such as counting or collecting city names, followed by a filter() or boolean condition to keep only the qualifying states. The Pandas engine performs the grouping in linear time with respect to the dataset size.

This mirrors the SQL approach conceptually and is common in data analysis workflows involving Pandas dataframes.

Recommended for interviews: The GROUP BY + HAVING solution is the expected answer. It demonstrates that you understand relational aggregation and how SQL filters aggregated groups. Window functions show deeper SQL knowledge, but the grouped aggregation approach is simpler, faster to write, and typically preferred in database interviews.

Solution

We can group the cities table by the state field, then apply filtering on each group to retain only the groups that meet the specified conditions.

Code

MySQLPandas

MySQL

Pandas

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
GROUP BY + HAVING AggregationO(n)O(k)Best general SQL solution for grouping rows by state and filtering aggregated results
Window Function + PartitionO(n)O(n)Useful when you need per-row data along with state-level statistics
Pandas groupby + filterO(n)O(k)Data analysis workflows using Python dataframes instead of SQL

Video Solution

Leetcode MEDIUM 3328 - Find Cities in Each State II - GROUP_CONCAT in SQL | Everyday Data Science • Everyday Data Science • 543 views views

Frequently Asked Questions

Is Find Cities in Each State II easy or hard?
Find Cities in Each State II is typically rated Medium because it requires understanding SQL aggregation and the difference between WHERE and HAVING filters. The query itself is short, but recognizing the correct grouping logic is the key step.
How to solve Find Cities in Each State II in O(n)?
Use GROUP BY on the state column and compute the required aggregate (such as city count). Apply the condition using HAVING to filter states that meet the criteria. Databases implement grouping with hashing or sorting, which keeps the overall complexity linear relative to the number of rows.
Find Cities in Each State II Python/Pandas solution
In Python, use Pandas with dataframe.groupby('state') to group rows. Then compute aggregates such as city counts and filter groups using boolean conditions or the filter() method. The logic mirrors SQL aggregation and runs in O(n) time.
What is the best approach for Find Cities in Each State II?
The most efficient solution uses SQL aggregation with GROUP BY and HAVING. You group rows by state, compute an aggregate such as COUNT of cities, and filter groups using HAVING. This approach runs in O(n) time and requires O(k) space where k is the number of distinct states.
Is Find Cities in Each State II asked at Google/Amazon/Meta?
Problems based on SQL aggregation and GROUP BY logic appear frequently in database interview rounds at companies like Amazon, Google, and Meta. Variations often involve filtering groups, ranking within partitions, or computing per-group statistics.
What data structure is used in Find Cities in Each State II?
Database engines internally use hash tables or sorting structures to build grouped aggregates. When you write a GROUP BY query, the engine groups rows by the state key and maintains aggregated values such as counts or lists of cities.
What is the time complexity of Find Cities in Each State II?
The typical SQL solution runs in O(n) time because the database scans the table once and aggregates rows by state. Space complexity is O(k) for storing intermediate groups, where k represents the number of unique states.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary