LeetCode 197: Rising Temperature

Problem Restatement

We are given a table named Weather.

Schema:

The id column is unique.

There are no duplicate recordDate values.

We need to find the id of every date where the temperature is higher than the temperature on the previous day.

Example table:

Expected output:

2015-01-02 is warmer than 2015-01-01.

2015-01-04 is warmer than 2015-01-03.

Input and Output

Examples

For this input:

Compare each row with the previous calendar date:

So the result is:

First Thought

We need to compare each row with another row in the same table.

That means we can use a self join.

Use one copy of the table as today:

Weather w1

Use another copy as yesterday:

Weather w2

Then match rows where w2.recordDate is exactly one day before w1.recordDate.

After that, keep only rows where today’s temperature is higher.

Key Insight

The key condition is not only that one date is earlier than another.

It must be exactly the previous day.

So this is correct:

DATEDIFF(w1.recordDate, w2.recordDate) = 1

This means w1.recordDate is one day after w2.recordDate.

Then we compare temperatures:

w1.temperature > w2.temperature

If both conditions are true, w1.id belongs in the answer.

Algorithm

Join the table with itself.

For each pair of rows:

1. Treat w1 as the current day.
2. Treat w2 as the previous day.
3. Check whether w1.recordDate is exactly one day after w2.recordDate.
4. Check whether w1.temperature is greater than w2.temperature.
5. Return w1.id.

Correctness

The join condition:

DATEDIFF(w1.recordDate, w2.recordDate) = 1

matches each row only with its previous calendar date.

Because the table has no duplicate recordDate values, a date can have at most one matching yesterday row.

The temperature condition:

w1.temperature > w2.temperature

keeps exactly the dates whose temperature is higher than the previous day.

Therefore, every returned id satisfies the problem requirement.

Any date that satisfies the requirement has a yesterday row and a higher temperature than that row, so it will be matched by the join and returned.

Complexity

Let n be the number of rows in Weather.

With an index on recordDate, a database engine can do this more efficiently.

Implementation

SELECT w1.id
FROM Weather w1
JOIN Weather w2
ON DATEDIFF(w1.recordDate, w2.recordDate) = 1
WHERE w1.temperature > w2.temperature;

Code Explanation

The query starts from the current-day row:

FROM Weather w1

Then it joins another copy of the same table:

JOIN Weather w2

The join condition finds yesterday:

ON DATEDIFF(w1.recordDate, w2.recordDate) = 1

For example:

DATEDIFF('2015-01-02', '2015-01-01') = 1

So 2015-01-02 is matched with 2015-01-01.

Then the WHERE clause keeps only warmer days:

WHERE w1.temperature > w2.temperature

Finally, the query returns the current day’s id:

SELECT w1.id

Testing

Create the table:

CREATE TABLE Weather (
    id INT,
    recordDate DATE,
    temperature INT
);

Insert sample data:

INSERT INTO Weather (id, recordDate, temperature) VALUES
(1, '2015-01-01', 10),
(2, '2015-01-02', 25),
(3, '2015-01-03', 20),
(4, '2015-01-04', 30);

Run the query:

SELECT w1.id
FROM Weather w1
JOIN Weather w2
ON DATEDIFF(w1.recordDate, w2.recordDate) = 1
WHERE w1.temperature > w2.temperature;

Expected output:

Test with a missing date:

Expected output is empty.

Even though 30 > 10, 2015-01-03 is not the day after 2015-01-01.