The First Day of the Maximum Recorded Degree in Each City - Solution & Explanation

Problem Overview: Each city has multiple temperature records across different days. For every city, return the first day when the maximum recorded degree occurred. If the maximum temperature appears multiple times, the earliest date should be returned.

Approach 1: Aggregation + Join (O(n) time, O(c) space)

Start by computing the maximum recorded degree for each city using GROUP BY city_id with MAX(degree). This produces a small result set containing one row per city with its peak temperature. Next, join this result back to the original table on both city_id and the matching maximum degree. Multiple rows may still exist if the same maximum degree appears on different days. To enforce the “first day” requirement, apply MIN(day) grouped by city_id. This approach relies on standard SQL operations—aggregation, join, and filtering—making it portable across most relational databases. The table scan for aggregation is O(n), and the grouped result size is proportional to the number of cities c, giving O(c) auxiliary space.

Approach 2: Window Function Filtering (O(n) time, O(n) space)

Another clean solution uses SQL window functions. Compute the maximum temperature per city with MAX(degree) OVER (PARTITION BY city_id). This annotates every row with the city’s maximum value without collapsing rows. Filter rows where degree = max_degree, leaving only records that match the peak temperature. Finally, select the earliest day using MIN(day) grouped by city_id. Window functions avoid a separate aggregation join and are often easier to read when supported by the database engine. The scan still processes each record once, giving O(n) time complexity, while storing window computation results leads to roughly O(n) space.

Both solutions rely on core SQL concepts such as GROUP BY, SQL joins, and window functions. The key insight is separating two concerns: identifying the maximum temperature per city, and selecting the earliest occurrence of that maximum.

Recommended for interviews: The aggregation + join approach is the most commonly expected answer. It shows that you understand grouping, joining derived tables, and resolving ties using MIN. The window function version is equally efficient but depends on familiarity with analytic functions, which some interviewers treat as an advanced SQL technique.