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.

Description Solution Video 4:18

2987. Find Expensive Cities

Easy77.1% acceptance1 companyPremium elsewhere, free here

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.

Asked at 1 company

Google

Topics

Database

4:18

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1

Input

{"headers":{"Listings":["listing_id","city","price"]},"rows":{"Listings":[[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]]}}

Your code is saved on this device.Solution