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.

3328. Find Cities in Each State II - Practice Online

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