Skip to main content
Talentd

Find Expensive Cities - Solution & Explanation

EasyPremiumFree on FleetCodeDatabase4 min readAsked at: Google
Practice this problem

Problem Statement

Table: Listings

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| listing_id  | int     |
| city        | varchar |
| price       | int     |
+-------------+---------+
listing_id is column of unique values for this table.
This table contains listing_id, city, and price.

Write a solution to find cities where the average home prices exceed the national average home price.

Return the result table sorted by city in ascending order.

The result format is in the following example.

 

Example 1:

Input: 
Listings table:
+------------+--------------+---------+
| listing_id | city         | price   | 
+------------+--------------+---------+
| 113        | LosAngeles   | 7560386 | 
| 136        | SanFrancisco | 2380268 |     
| 92         | Chicago      | 9833209 | 
| 60         | Chicago      | 5147582 | 
| 8          | Chicago      | 5274441 |  
| 79         | SanFrancisco | 8372065 | 
| 37         | Chicago      | 7939595 | 
| 53         | LosAngeles   | 4965123 | 
| 178        | SanFrancisco | 999207  | 
| 51         | NewYork      | 5951718 | 
| 121        | NewYork      | 2893760 | 
+------------+--------------+---------+
Output
+------------+
| city       | 
+------------+
| Chicago    | 
| LosAngeles |  
+------------+
Explanation
The national average home price is $6,122,059.45. Among the cities listed:
- Chicago has an average price of $7,048,706.75
- Los Angeles has an average price of $6,277,754.5
- San Francisco has an average price of $3,900,513.33
- New York has an average price of $4,422,739
Only Chicago and Los Angeles have average home prices exceeding the national average. Therefore, these two cities are included in the output table. The output table is sorted in ascending order based on the city names.

Approach Overview

Problem Overview: You are given a table of property listings with a city and price. The task is to return cities where the average listing price is higher than the overall average price across all listings.

Approach 1: Correlated Subquery per City (O(n^2) time, O(1) space)

A straightforward approach calculates the average price for each city and compares it against the global average using a correlated subquery. For every city group, the query recomputes the overall average price. While logically simple, the repeated subquery execution can cause unnecessary scans on large datasets. This pattern appears often in early SQL solutions but becomes inefficient as the table grows.

Approach 2: Grouping Aggregation + Subquery (O(n) time, O(1) space)

The cleaner solution uses GROUP BY to compute the average price for each city, then compares it against a single global average computed in a subquery. The key insight: the overall average does not depend on the city group, so it should be calculated once. The database engine scans the listings table to compute the global average, then performs a grouped aggregation by city and filters using a HAVING condition such as AVG(price) > (SELECT AVG(price) FROM listings). This reduces redundant work and keeps the query readable.

This pattern is common in SQL interview questions involving relative comparisons, where a group metric is compared with a dataset-wide metric. It relies heavily on SQL aggregation features such as GROUP BY, AVG(), and HAVING. Understanding how aggregation works internally is key when solving database problems. The same structure appears frequently in problems involving department averages, product pricing, or user activity statistics, all based on aggregation logic.

Recommended for interviews: The grouping aggregation with a subquery is the expected solution. It demonstrates that you understand SQL aggregation, dataset-level metrics, and filtering grouped results using HAVING. The naive correlated approach shows the correct intuition, but the optimized aggregation query shows stronger SQL fluency.

Solution

We group the Listings table by city, then calculate the average house price for each city, and finally filter out the cities where the average house price is greater than the national average house price.

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Correlated Subquery per CityO(n^2)O(1)Conceptual solution when learning SQL subqueries; not ideal for large tables
Grouping Aggregation + SubqueryO(n)O(1)Best approach for SQL interviews and production queries comparing group metrics to global metrics

Video Solution

Leetcode 2987 - Find Expensive Cities - Solved by Everyday Data Science | WINDOW Functions • Everyday Data Science • 607 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Find Expensive Cities easy or hard?
Find Expensive Cities is considered an Easy database problem. The main concept is understanding SQL aggregation and using HAVING with a subquery to compare grouped results against a dataset-wide average.
Find Expensive Cities Python/Java solution
The problem is designed to be solved using SQL rather than Python or Java. Instead of writing application code, you write a SQL query using GROUP BY and a subquery to compare each city's average price against the global average.
How to solve Find Expensive Cities in O(n)?
Use GROUP BY city to compute AVG(price) for each city and compare it against a single global average computed using a subquery: SELECT city FROM listings GROUP BY city HAVING AVG(price) > (SELECT AVG(price) FROM listings). The database performs a linear scan for aggregation, resulting in near O(n) complexity.
What is the best approach for Find Expensive Cities?
The best solution uses SQL aggregation with GROUP BY and a subquery. First compute the average price per city using AVG(price) and GROUP BY city. Then compare it against the global average price using a subquery inside a HAVING clause. This avoids repeated scans and keeps the query efficient.
Is Find Expensive Cities asked at Google/Amazon/Meta?
SQL aggregation problems similar to Find Expensive Cities appear frequently in data-focused interview rounds at companies like Amazon, Meta, and Google. They test understanding of GROUP BY, HAVING filters, and comparing group metrics against overall dataset statistics.
What data structure is used in Find Expensive Cities?
This is a database query problem rather than a traditional data structure problem. It relies on SQL aggregation functions such as AVG() and grouping with GROUP BY. Internally, database engines often use hash aggregation or sorting to compute grouped results efficiently.
What is the time complexity of Find Expensive Cities?
The optimized SQL solution runs in roughly O(n) time where n is the number of rows in the listings table. The database scans the table once to compute the overall average and once for the grouped aggregation. Space complexity is O(1) because only aggregate values are stored.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary