197. Rising Temperature
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 40.2%
Problem Breakdown
The problem “Rising Temperature” asks us to find all records from a table named Weather where the temperature of a given day is higher than the temperature of the previous day. The input is a table with at least two columns: id, which uniquely identifies each record, and temperature, which represents the temperature on that day. Additionally, there’s a column recordDate which indicates the date of the record.
Inputs:
- A table
Weatherwith columnsid,temperature, andrecordDate.
Outputs:
- A list of records from the
Weathertable where the temperature is higher than the previous day’s temperature.
Implicit Constraints/Tricky Edge Cases:
- The table might be empty.
- There could be duplicate temperatures on consecutive days, which should not be included in the output.
- The dates are provided but not necessarily sorted; they need to be considered in chronological order.
Intuition
To solve this problem, we first consider a brute-force approach where we sort the records by date and then iterate through them to compare each day’s temperature with the previous day’s. However, this approach would require sorting the entire table, which could be inefficient for large datasets.
A more efficient approach involves using self-joins in SQL. By joining the Weather table with itself on the condition that the current record’s date is exactly one day after the previous record’s date, we can directly compare temperatures without needing to sort the entire dataset.
Approach
- Self-Join: Perform a self-join on the
Weathertable where the join condition is that therecordDateof the first table (t1) is exactly one day before therecordDateof the second table (t2). - Filter by Temperature: After joining, filter the results to include only those records where the temperature in
t2(the current day) is higher than the temperature int1(the previous day). - Select Required Columns: Select the required columns from the filtered results.
Complexity Analysis
- Time Complexity: The time complexity of this solution is O(n log n) due to the implicit sorting operation that occurs during the join, where n is the number of records in the
Weathertable. - Space Complexity: The space complexity is O(n) as we are storing the results of the join operation.
Solution
SELECT w1.id AS id
FROM Weather w1, Weather w2
WHERE DATEDIFF(w1.recordDate, w2.recordDate) = 1 AND w1.temperature < w2.temperature;
Edge Cases Handled
- Empty Table: If the
Weathertable is empty, the query will return an empty result set. - Consecutive Days with Same Temperature: The condition
w1.temperature < w2.temperatureensures that only days with a higher temperature are included in the results. - Unsorted Dates: The use of
DATEDIFF(w1.recordDate, w2.recordDate) = 1ensures that we are comparing consecutive days regardless of the initial order of records.