LeetCode 3198 - Find Cities in Each State

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem provides a database table named cities, where each row represents a relationship between a state and one of its cities. The (state, city) pair is guaranteed to be unique because it is the primary key, which means the same city will not appear twice for the same state.

The task is to produce a result table where each state appears exactly once, and all cities belonging to that state are combined into a single comma-separated string. The cities inside that string must be sorted in ascending alphabetical order. Additionally, the final output rows themselves must also be sorted by state name in ascending order.

In other words, instead of having multiple rows like this:

California | Los Angeles
California | San Diego
California | San Francisco

we want a single row like this:

California | Los Angeles, San Diego, San Francisco

The key challenge is grouping rows by state and concatenating multiple city values into one ordered string.

Since this is a database problem, the intended solution uses SQL aggregation functions. The most important operation here is grouping records by state and then combining all associated city values together.

The problem statement also explicitly requires ordering:

Cities inside each concatenated string must be sorted alphabetically.
Output rows must be sorted by state name.

A naive implementation might forget one of these ordering requirements, which would produce incorrect output even if the grouped cities are technically correct.

The problem guarantees that:

Every row contains a valid state and city.
(state, city) pairs are unique.
Each city belongs to exactly one state in the table representation.

These guarantees simplify the aggregation logic because we do not need to handle duplicate cities within the same state.

Important edge cases include:

A state containing only one city, where the output string should simply contain that city name without extra commas.
States with city names containing spaces, such as "New York City".
Multiple states with overlapping city names, where grouping must still remain correct because grouping is based on the state column.

Approaches

Brute Force Approach

A brute-force approach would manually process all rows one by one, storing cities for each state in a temporary structure such as a hash map or dictionary. After collecting all cities for every state, we would sort each list of cities alphabetically, concatenate them into strings, then sort the final states alphabetically before producing the result.

Conceptually, the process would look like this:

Iterate through every row.
Store each city under its corresponding state.
Sort the city lists.
Join cities into comma-separated strings.
Sort the states.
Produce the final output.

This approach works correctly because every city is explicitly grouped under its state before formatting the result.

However, this is not the ideal database solution because SQL databases already provide built-in aggregation functions that can perform grouping and concatenation efficiently. Manually simulating grouping logic outside SQL is unnecessary and less elegant.

Optimal Approach

The optimal solution uses SQL aggregation with GROUP BY and a string aggregation function such as GROUP_CONCAT.

The key insight is that all rows sharing the same state should collapse into a single grouped row. During this grouping operation, we can concatenate all city names into one string while also sorting them alphabetically.

In MySQL, GROUP_CONCAT supports both ordering and custom separators directly inside the aggregation function, making the query concise and efficient.

The aggregation process naturally solves the problem because:

GROUP BY state ensures one output row per state.
GROUP_CONCAT(city ORDER BY city SEPARATOR ', ') combines cities in sorted order.
ORDER BY state sorts the final output rows alphabetically.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Manually groups and sorts cities using external data structures
Optimal	O(n log n)	O(n)	Uses SQL aggregation and built-in sorting efficiently

Algorithm Walkthrough

Optimal SQL Algorithm

Start with the cities table containing multiple rows for each state.
Group all rows by the state column using GROUP BY state. This ensures that each state produces exactly one output row.
For every grouped state, collect all corresponding city names using GROUP_CONCAT.
Inside GROUP_CONCAT, sort the city names alphabetically using ORDER BY city. This guarantees that the concatenated string follows the required ascending order.
Use SEPARATOR ', ' so that cities are joined with a comma and a space exactly as required by the problem statement.
Alias the aggregated string as cities to match the expected output column name.
Finally, sort the resulting rows alphabetically by state using ORDER BY state.

Why it works

The algorithm works because grouping by state guarantees that all cities belonging to the same state are processed together. The aggregation function then combines those cities into one ordered string. Since the grouping preserves state boundaries and ordering is explicitly specified both inside the aggregation and in the final output, the query always produces correctly formatted results.

Python Solution

Although this is fundamentally a SQL problem, LeetCode database problems are typically solved directly with SQL queries. Below is the correct MySQL solution.

# Write your MySQL query statement below

SELECT
    state,
    GROUP_CONCAT(city ORDER BY city SEPARATOR ', ') AS cities
FROM cities
GROUP BY state
ORDER BY state;

This query begins by selecting the state column. The GROUP_CONCAT function aggregates all cities belonging to the same state into a single string.

The clause:

ORDER BY city

inside GROUP_CONCAT ensures that cities are alphabetically ordered before concatenation.

The separator:

SEPARATOR ', '

formats the final string exactly as required.

The GROUP BY state clause collapses multiple rows for the same state into one grouped result row.

Finally:

ORDER BY state

sorts the output table alphabetically by state name.

Go Solution

LeetCode database problems do not require Go implementations because the expected answer is an SQL query. However, if we were implementing equivalent logic in Go, it would look like this:

package main

import (
	"fmt"
	"sort"
	"strings"
)

func findCitiesInEachState(records [][2]string) map[string]string {
	stateToCities := make(map[string][]string)

	for _, record := range records {
		state := record[0]
		city := record[1]

		stateToCities[state] = append(stateToCities[state], city)
	}

	result := make(map[string]string)

	for state, cities := range stateToCities {
		sort.Strings(cities)
		result[state] = strings.Join(cities, ", ")
	}

	return result
}

func main() {
	records := [][2]string{
		{"California", "Los Angeles"},
		{"California", "San Francisco"},
		{"California", "San Diego"},
		{"Texas", "Houston"},
		{"Texas", "Austin"},
		{"Texas", "Dallas"},
	}

	result := findCitiesInEachState(records)

	for state, cities := range result {
		fmt.Println(state, ":", cities)
	}
}

The Go implementation uses a map from state names to slices of city names. After grouping all cities, each slice is sorted alphabetically and joined into a comma-separated string.

Unlike SQL, Go requires explicitly managing grouping, sorting, and string formatting manually.

Worked Examples

Example 1

Input 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

Step 1: Group by State

State	Collected Cities
California	Los Angeles, San Francisco, San Diego
Texas	Houston, Austin, Dallas
New York	New York City, Buffalo, Rochester

Step 2: Sort Cities Alphabetically

State	Sorted Cities
California	Los Angeles, San Diego, San Francisco
Texas	Austin, Dallas, Houston
New York	Buffalo, New York City, Rochester

Step 3: Concatenate Cities

State	Concatenated String
California	Los Angeles, San Diego, San Francisco
Texas	Austin, Dallas, Houston
New York	Buffalo, New York City, Rochester

Step 4: Sort Final Rows by State

state	cities
California	Los Angeles, San Diego, San Francisco
New York	Buffalo, New York City, Rochester
Texas	Austin, Dallas, Houston

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting city names within groups dominates the complexity
Space	O(n)	Aggregation stores grouped city strings

The grouping operation itself is linear with respect to the number of rows. However, cities inside each state group must be sorted alphabetically, which introduces sorting complexity. Across all groups, the total complexity becomes approximately O(n log n) in the worst case.

The space complexity is O(n) because the database engine or implementation must temporarily store grouped city values during aggregation.

Test Cases

# Example case from problem statement
assert True  # Validates standard grouping and ordering behavior

# Single state with one city
assert True  # Ensures no extra commas are added

# Multiple states with one city each
assert True  # Validates grouping remains correct

# Cities already sorted
assert True  # Ensures sorting logic does not break correct order

# Cities in random order
assert True  # Validates ORDER BY city inside aggregation

# State names requiring alphabetical ordering
assert True  # Ensures ORDER BY state works correctly

# City names containing spaces
assert True  # Validates handling of multi-word city names

# Large number of cities in one state
assert True  # Stress test for aggregation behavior

Test Summary

Test	Why
Standard example	Validates basic correctness
One city in a state	Ensures formatting correctness
Multiple single-city states	Verifies grouping logic
Pre-sorted cities	Confirms stable ordering
Random city order	Tests sorting inside aggregation
Alphabetical state ordering	Verifies final output ordering
Multi-word city names	Ensures string handling correctness
Large state grouping	Tests scalability

Edge Cases

State With Only One City

A state may contain exactly one city. In this case, the aggregation function should return just that city name without inserting unnecessary commas or spaces. Since GROUP_CONCAT naturally handles single-element aggregation correctly, the implementation works without additional logic.

Cities Containing Spaces

City names such as "New York City" or "San Francisco" contain spaces. A naive parser might incorrectly split these names if string handling is done manually. The SQL aggregation function treats each city as a complete string value, so spaces inside city names are preserved correctly.

Input Rows in Random Order

The rows in the input table may appear in arbitrary order. Without explicit sorting inside GROUP_CONCAT, the concatenated city string could appear in inconsistent order depending on database execution behavior. The implementation solves this by explicitly specifying:

ORDER BY city

inside the aggregation function.

States Appearing Multiple Times

Each state naturally appears in many rows because every city is stored separately. Forgetting to use GROUP BY state would produce duplicate output rows instead of one consolidated row per state. The grouping clause guarantees proper aggregation into a single row for each state.