Find Expensive Cities - Solution & Explanation

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.