Table: Weather
+---------------+---------+ | Column Name | Type | +---------------+---------+ | id | int | | recordDate | date | | temperature | int | +---------------+---------+ id is the column with unique values for this table. There are no different rows with the same recordDate. This table contains information about the temperature on a certain day.
Write a solution to find all dates' id with higher temperatures compared to its previous dates (yesterday).
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Weather table: +----+------------+-------------+ | id | recordDate | temperature | +----+------------+-------------+ | 1 | 2015-01-01 | 10 | | 2 | 2015-01-02 | 25 | | 3 | 2015-01-03 | 20 | | 4 | 2015-01-04 | 30 | +----+------------+-------------+ Output: +----+ | id | +----+ | 2 | | 4 | +----+ Explanation: In 2015-01-02, the temperature was higher than the previous day (10 -> 25). In 2015-01-04, the temperature was higher than the previous day (20 -> 30).
Problem Overview: The Rising Temperature problem asks you to return the id of days where the temperature is higher than the previous day's temperature. The table Weather(id, recordDate, temperature) stores daily weather data, and the task is to compare each day's temperature with the temperature from exactly one day earlier.
Approach 1: Self-Join Approach (O(n) time, O(1) extra space)
This method joins the Weather table with itself. One copy represents the current day and the other represents the previous day. The key idea is matching rows where DATEDIFF(current.recordDate, previous.recordDate) = 1. After the join, filter rows where current.temperature > previous.temperature. This works because the join aligns each day with its immediate predecessor, allowing a direct comparison of temperatures. The approach is straightforward and widely supported in SQL engines.
Approach 2: Self-Join on Dates (O(n) time, O(1) extra space)
A variation of the self-join uses date arithmetic instead of DATEDIFF. Join the table where w1.recordDate = DATE_ADD(w2.recordDate, INTERVAL 1 DAY). Once the rows are aligned by consecutive dates, check if w1.temperature > w2.temperature. This approach is easy to read because the relationship between rows is explicit: one row is exactly one day after the other. Many SQL interview problems rely on this pattern of joining rows based on relative dates.
Approach 3: Using LAG Window Function (O(n) time, O(1) extra space)
Window functions provide a cleaner and often more modern solution. Using LAG(temperature), you can access the temperature from the previous row while scanning the table ordered by recordDate. Each row compares its temperature with the lagged value and returns the id if the current temperature is higher and the date difference is exactly one day. This approach avoids joins and makes the query shorter and easier to reason about. It relies on concepts from SQL window operations.
Approach 4: General Window Functions Strategy (O(n) time, O(1) extra space)
You can extend the window function idea by computing both the previous temperature and previous date using LAG(). Then filter rows where temperature > prev_temp and DATEDIFF(recordDate, prev_date) = 1. This pattern is useful when working with ordered datasets in database queries and is a common technique when solving problems involving sequential comparisons with window functions.
Recommended for interviews: The self-join approach demonstrates that you understand relational joins and date comparisons, which is often expected in SQL interviews. The window function solution using LAG() is usually considered the cleanest and most modern approach. Showing the join first and then optimizing with a window function signals strong SQL problem-solving skills.
This approach uses SQL's self-join capabilities. We join the Weather table with itself by matching the current day's date with the day after the previous date, effectively allowing us to compare temperatures between consecutive days.
This way, we filter for cases where the current day's temperature is higher than the previous day's temperature.
The SQL code joins the Weather table with itself. For each record in the first instance (w1), it compares with records in the second instance (w2) where the difference in days (DATEDIFF) is exactly one, meaning consecutive days. Then, it filters those records where the temperature of w1 is greater than w2.
Time Complexity: O(n), where n is the number of records, as we are checking each record with its previous day's record.
Space Complexity: O(1), as no extra space is used except for the result set.
This approach utilizes SQL window functions, specifically the LAG function, which allows you to access the value of a column from the previous row.
We use LAG to find the previous day's temperature for each record and then filter the results where the current day's temperature is higher than the previous day's temperature.
The SQL code first creates a subquery with the Weather data, adding a new column prev_temp using the LAG window function. LAG(temperature, 1) gives the temperature of the previous day. Then, the outer query selects rows where the current day's temperature is greater than prev_temp.
Time Complexity: O(n), due to scanning through all rows once with window function.
Space Complexity: O(n), due to the subquery which temporarily holds additional columns.
This approach involves performing a self-join on the Weather table. We join the table with itself where the recordDate of the second table (alias W2) is one day earlier than the recordDate of the first table (alias W1). This allows us to compare the temperatures of each date with its previous day.
This SQL solution utilizes a self-join to compare the temperature of each day with its previous day. We join the Weather table with itself using the condition that W1's recordDate should be exactly one day after W2's recordDate. Then, we select the IDs where W1's temperature is greater than W2's temperature.
Time Complexity: O(n log n) due to the use of joins, assuming a general sort operation for join implementation. Space Complexity: O(n) for storing join results.
This approach leverages window functions to compare each day's temperature with the previous day's temperature without explicitly joining the table. By using the LAG function, we can access the previous record's temperature for comparison.
This solution employs the LAG window function to access the temperature of the previous day for each record. We create a subquery that includes a column for the previous day's temperature calculated by LAG. Finally, we filter where the current temperature is greater than the previous day's temperature.
Time Complexity: O(n) as window functions efficiently traverse the data in one pass. Space Complexity: O(n) to store intermediate results of window functions.
| Approach | Complexity |
|---|---|
| Self-Join Approach | Time Complexity: O(n), where n is the number of records, as we are checking each record with its previous day's record. |
| Using Lag Window Function | Time Complexity: O(n), due to scanning through all rows once with window function. |
| Self-Join on Dates | Time Complexity: O(n log n) due to the use of joins, assuming a general sort operation for join implementation. Space Complexity: O(n) for storing join results. |
| Using Window Functions | Time Complexity: O(n) as window functions efficiently traverse the data in one pass. Space Complexity: O(n) to store intermediate results of window functions. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Self-Join Approach | O(n) | O(1) | Classic SQL solution when window functions are unavailable |
| Self-Join on Dates | O(n) | O(1) | Readable query using explicit date relationships |
| LAG Window Function | O(n) | O(1) | Preferred modern SQL approach for sequential row comparison |
| General Window Functions Strategy | O(n) | O(1) | Useful when multiple previous-row values are needed |
Daily Temperatures - Monotonic Stack - Leetcode 739 - Python • NeetCode • 264,314 views views
Watch 9 more video solutions →Practice Rising Temperature with our built-in code editor and test cases.
Practice on FleetCode