LeetCode 2314 - The First Day of the Maximum Recorded Degree in Each City

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem gives us a database table named Weather that stores temperature readings for different cities on specific days in the year 2022.

Each row contains three values:

city_id, which identifies the city
day, which represents the date of the measurement
degree, which represents the recorded temperature

The pair (city_id, day) is guaranteed to be unique, meaning a city cannot have multiple temperature records for the same day.

The task is to find, for every city, the day on which the maximum temperature was recorded. If the same maximum temperature appears multiple times for a city, we must return the earliest day among those occurrences.

The output should contain:

city_id
day
degree

The final result must be sorted by city_id in ascending order.

The key detail in this problem is the tie-breaking rule. Finding the maximum degree alone is not enough. If multiple rows share the same maximum degree, we must choose the earliest date.

For example, suppose a city has:

city_id	day	degree
2	2022-08-07	37
2	2022-08-17	37

Both rows have the maximum temperature of 37, but the correct answer is 2022-08-07 because it is earlier.

The constraints imply that we are working with relational database operations rather than in-memory algorithmic structures. This means the solution should use SQL features efficiently, particularly aggregation and ranking.

Several edge cases are important:

A city may have only one weather record
Multiple rows may share the same maximum degree
Degrees can be negative
The earliest date must be selected correctly among ties
Different cities are completely independent and must be processed separately

Because the primary key guarantees unique (city_id, day) pairs, we never need to worry about duplicate rows for the same city and date.

Approaches

Brute Force Approach

A brute-force strategy would process each city independently.

For every city, we could first determine the maximum degree by scanning all rows belonging to that city. Then we could scan the same rows again to find the earliest date that matches that maximum degree.

Conceptually, this works because:

The first pass identifies the target temperature
The second pass applies the tie-breaking rule

In SQL, this might involve nested subqueries or repeated scans of the table.

Although correct, this approach is inefficient because it repeatedly searches through the same data. If there are many cities and many records per city, the database engine performs unnecessary repeated work.

Optimal Approach

The better solution uses a window function, specifically ROW_NUMBER().

The key insight is that we can rank rows inside each city according to:

Highest degree first
Earliest day first

If we sort rows this way, then the first row in each city partition is exactly the answer we want.

This works perfectly because:

Ordering by degree DESC ensures the maximum temperature appears first
Ordering by day ASC resolves ties by choosing the earliest date
ROW_NUMBER() lets us select exactly one row per city

This approach is efficient because the database handles grouping, sorting, and ranking in a single pass over the data partitions.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeated scans for each city
Optimal	O(n log n)	O(n)	Uses window functions and partitioned sorting

Algorithm Walkthrough

Partition the rows by city_id.

This ensures that each city is processed independently. Weather records from different cities should never affect one another. 2. Inside each city partition, sort the rows by degree in descending order.

This places the highest temperature at the top of the partition. 3. If multiple rows have the same degree, sort those rows by day in ascending order.

This guarantees that among equal maximum temperatures, the earliest date comes first. 4. Apply the ROW_NUMBER() window function.

The first row in each partition receives rank 1, the second row receives rank 2, and so on. 5. Select only rows where the row number equals 1.

Since the rows are already sorted correctly, the row with rank 1 is exactly the desired answer for that city. 6. Order the final result by city_id.

This satisfies the output requirement in the problem statement.

Why it works

The correctness comes from the ordering criteria used inside each city partition.

By sorting first by descending temperature, we ensure the maximum degree always appears before smaller values. By sorting ties using ascending dates, we ensure the earliest occurrence of that maximum degree appears first.

Therefore, the row assigned ROW_NUMBER() = 1 must be the unique correct answer for that city.

Python Solution

# Write your MySQL query statement below

SELECT city_id, day, degree
FROM (
    SELECT
        city_id,
        day,
        degree,
        ROW_NUMBER() OVER (
            PARTITION BY city_id
            ORDER BY degree DESC, day ASC
        ) AS rn
    FROM Weather
) ranked_weather
WHERE rn = 1
ORDER BY city_id;

The query begins by creating a derived table named ranked_weather.

Inside this derived table, the ROW_NUMBER() window function assigns a ranking to every weather record within each city. The PARTITION BY city_id clause ensures that rankings restart for every city.

The ordering rule is the most important part of the solution:

ORDER BY degree DESC, day ASC

This first prioritizes higher temperatures and then resolves ties using earlier dates.

After ranking all rows, the outer query filters the results to only rows where rn = 1. Those rows represent the best candidate for each city according to the problem requirements.

Finally, the result is sorted by city_id in ascending order.

Go Solution

// Write your MySQL query statement below

SELECT city_id, day, degree
FROM (
    SELECT
        city_id,
        day,
        degree,
        ROW_NUMBER() OVER (
            PARTITION BY city_id
            ORDER BY degree DESC, day ASC
        ) AS rn
    FROM Weather
) ranked_weather
WHERE rn = 1
ORDER BY city_id;

Unlike traditional algorithmic LeetCode problems, this database problem does not require an actual Go implementation with data structures or loops. LeetCode expects a SQL query submission even when viewing the problem under different language tabs.

Therefore, the same SQL solution applies regardless of whether the selected language is Python, Go, Java, or another language.

Worked Examples

Example 1

Input table:

city_id	day	degree
1	2022-01-07	-12
1	2022-03-07	5
1	2022-07-07	24
2	2022-08-07	37
2	2022-08-17	37
3	2022-02-07	-7
3	2022-12-07	-6

After partitioning by city and sorting:

City 1

day	degree	rank
2022-07-07	24	1
2022-03-07	5	2
2022-01-07	-12	3

The row with rank 1 is selected.

City 2

day	degree	rank
2022-08-07	37	1
2022-08-17	37	2

Both rows have the same degree, so the earlier date receives the smaller rank.

City 3

day	degree	rank
2022-12-07	-6	1
2022-02-07	-7	2

Even though both temperatures are negative, -6 is greater than -7, so it becomes the maximum degree.

Final output:

city_id	day	degree
1	2022-07-07	24
2	2022-08-07	37
3	2022-12-07	-6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Rows are sorted within partitions
Space	O(n)	Window function processing may require auxiliary storage

The dominant cost comes from sorting rows for each city partition. Window functions internally maintain ordered partitions, which typically leads to O(n log n) complexity.

The space complexity depends on the database engine implementation, but window functions generally require temporary storage for partition ordering and ranking.

Test Cases

# Example case with tie on maximum degree
assert solution == [
    [1, "2022-07-07", 24],
    [2, "2022-08-07", 37],
    [3, "2022-12-07", -6]
]

# Single city with one row
assert solution == [
    [1, "2022-01-01", 10]
]

# Multiple maximum degrees, earliest date should win
assert solution == [
    [1, "2022-01-01", 20]
]

# Negative temperatures only
assert solution == [
    [1, "2022-02-01", -3]
]

# Multiple cities with independent rankings
assert solution == [
    [1, "2022-01-01", 15],
    [2, "2022-05-01", 30]
]

# Maximum degree appears at the end
assert solution == [
    [1, "2022-12-31", 100]
]

# Earliest date tie-breaking validation
assert solution == [
    [5, "2022-03-01", 50]
]

Test	Why
Example with tie	Verifies tie-breaking logic
Single row city	Ensures trivial case works
Repeated maximum	Confirms earliest date selection
Negative temperatures	Validates comparison correctness
Multiple cities	Ensures partitions are independent
Maximum at end	Confirms sorting correctness
Tie-breaking validation	Ensures ascending date ordering

Edge Cases

One important edge case occurs when a city has only one weather record. In this situation, that row must automatically be the answer because it is both the maximum degree and the earliest occurrence. The implementation handles this naturally because ROW_NUMBER() assigns rank 1 to the only row in the partition.

Another critical edge case happens when multiple rows share the same maximum degree. A naive solution that only computes MAX(degree) could accidentally return multiple rows or choose an arbitrary row. The implementation avoids this by sorting tied rows using day ASC, ensuring the earliest date always receives rank 1.

Negative temperatures are also important. Some incorrect implementations may assume temperatures are non-negative or mishandle comparisons involving negative numbers. Since SQL numeric comparisons work correctly for negative integers, ordering by degree DESC still correctly identifies the largest temperature value, even if all values are below zero.

A final edge case involves cities with many records spread throughout the year. The maximum temperature could appear near the beginning, middle, or end of the dataset. Because the solution uses partitioned sorting rather than relying on insertion order, it correctly identifies the maximum regardless of where the row appears in the table.