LeetCode 197 - Rising Temperature

The problem gives us a database table named Weather that stores daily temperature records. Each row contains three fields: a unique id, a recordDate, and the temperature recorded on that date.

leetcodeeasydatabase

LeetCode Problem 197

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem gives us a database table named Weather that stores daily temperature records. Each row contains three fields: a unique id, a recordDate, and the temperature recorded on that date.

The task is to find all rows where the temperature is higher than the temperature recorded on the previous calendar day. In other words, for each date, we must determine whether yesterday exists in the table and whether today's temperature is strictly greater than yesterday's temperature. If both conditions are true, we return the current row's id.

For example, suppose we have a row for 2015-01-02 with temperature 25, and another row for 2015-01-01 with temperature 10. Since 25 > 10, the row for 2015-01-02 qualifies, so we include its id.

An important detail is that the comparison must be with the immediately previous calendar day, not simply the previous row in sorted order. If a date is missing from the table, then there is no valid "yesterday" entry for comparison.

The problem guarantees that:

  • id values are unique
  • No two rows share the same recordDate
  • Each row represents exactly one day's temperature

These guarantees simplify the solution because we never need to handle duplicate dates or ambiguous comparisons.

The scale of the problem is small enough that even less efficient solutions may pass, but the goal is to write a clean and optimal SQL query.

Several edge cases are important:

  • The earliest date in the table can never qualify because it has no previous day.
  • Missing dates matter. If 2015-01-03 exists but 2015-01-02 does not, then 2015-01-03 cannot be compared and should not be included.
  • Equal temperatures do not qualify because the problem requires strictly higher temperatures.
  • The table may contain only one row, in which case the result is empty.

Approaches

Brute Force Approach

A brute-force solution would examine every row and search the entire table to find whether a row exists for the previous calendar day. Once found, it would compare temperatures.

Conceptually, for every record:

  1. Compute yesterday's date.
  2. Scan all rows to find a matching date.
  3. Compare temperatures.
  4. Add the current id if today's temperature is greater.

This approach is correct because every row explicitly checks whether a valid previous-day record exists and whether the temperature condition holds.

However, this solution is inefficient because each row may require scanning the entire table again. If there are n rows, the total work becomes O(n²).

Optimal Approach

The key insight is that this is naturally a self-join problem.

We need to compare each row with another row from the same table, specifically the row representing yesterday. SQL joins are designed exactly for this type of relationship.

We can join the Weather table with itself:

  • One alias represents today's weather
  • Another alias represents yesterday's weather

Then we enforce two conditions:

  1. The dates differ by exactly one day
  2. Today's temperature is greater than yesterday's temperature

Because database engines optimize joins efficiently, this approach avoids repeated full scans and is much cleaner conceptually.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) For every row, scan the table again to find yesterday
Optimal O(n) average with indexing O(1) Uses a self-join to directly compare adjacent dates

Algorithm Walkthrough

  1. Start by creating two aliases of the Weather table.

One alias represents the current day's record, usually called w1. The second alias represents the previous day's record, usually called w2. 2. Match rows where the dates differ by exactly one day.

We use a date function such as DATEDIFF(w1.recordDate, w2.recordDate) = 1.

This ensures that w2 is exactly yesterday relative to w1. 3. Compare temperatures.

After matching adjacent dates, check whether:

w1.temperature > w2.temperature

This filters only the rows where the temperature increased. 4. Return the current day's id.

The problem asks for the id corresponding to the warmer day, so we select w1.id.

Why it works

The algorithm works because every qualifying row must satisfy two independent conditions:

  • There exists a row exactly one calendar day earlier
  • The current temperature is greater than the previous day's temperature

The self-join guarantees that only valid adjacent-day pairs are compared. The temperature filter then ensures only rising temperatures are returned. Since each date is unique, every comparison is unambiguous.

Python Solution

Although this is a database problem and LeetCode expects SQL, the following Python example demonstrates the same logic programmatically.

from typing import List, Dict

class Solution:
    def risingTemperature(self, weather: List[Dict]) -> List[int]:
        date_to_temp = {}
        date_to_id = {}

        for record in weather:
            date_to_temp[record["recordDate"]] = record["temperature"]
            date_to_id[record["recordDate"]] = record["id"]

        result = []

        for record in weather:
            current_date = record["recordDate"]
            current_temp = record["temperature"]

            previous_date = current_date.fromordinal(
                current_date.toordinal() - 1
            )

            if previous_date in date_to_temp:
                if current_temp > date_to_temp[previous_date]:
                    result.append(record["id"])

        return result

After building hash maps from dates to temperatures and IDs, the implementation iterates through each record and computes the previous calendar day. If yesterday exists in the dataset and today's temperature is higher, the current id is added to the result.

The hash map allows constant-time lookup for yesterday's temperature, avoiding the repeated scanning required in the brute-force approach.

For the actual LeetCode database submission, the expected SQL solution is:

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

This SQL query directly mirrors the algorithmic reasoning discussed earlier.

Go Solution

package main

import (
	"time"
)

type WeatherRecord struct {
	ID          int
	RecordDate  time.Time
	Temperature int
}

func risingTemperature(weather []WeatherRecord) []int {
	dateToTemp := make(map[time.Time]int)

	for _, record := range weather {
		dateToTemp[record.RecordDate] = record.Temperature
	}

	result := []int{}

	for _, record := range weather {
		previousDate := record.RecordDate.AddDate(0, 0, -1)

		if previousTemp, exists := dateToTemp[previousDate]; exists {
			if record.Temperature > previousTemp {
				result = append(result, record.ID)
			}
		}
	}

	return result
}

The Go implementation follows the same strategy as the Python version. A map provides constant-time access to yesterday's temperature.

One Go-specific detail is the use of time.Time and AddDate(0, 0, -1) to compute the previous day. Slices are used dynamically for the result list, and Go's map lookup syntax conveniently returns both the value and whether the key exists.

Worked Examples

Example 1

Input table:

id recordDate temperature
1 2015-01-01 10
2 2015-01-02 25
3 2015-01-03 20
4 2015-01-04 30

The algorithm compares each row with the previous calendar day.

Current Date Current Temp Previous Date Previous Temp Rising? Output ID
2015-01-01 10 2014-12-31 Not Found No -
2015-01-02 25 2015-01-01 10 Yes 2
2015-01-03 20 2015-01-02 25 No -
2015-01-04 30 2015-01-03 20 Yes 4

Final result:

id
2
4

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row is processed once with constant-time lookups
Space O(n) The hash map stores temperatures indexed by date

The SQL self-join is typically optimized internally by the database engine, especially if indexes exist on recordDate. In the programmatic implementations, hash maps allow direct lookup of yesterday's temperature in constant time, producing linear overall complexity.

Test Cases

from datetime import date

solution = Solution()

# Basic example from the prompt
weather1 = [
    {"id": 1, "recordDate": date(2015, 1, 1), "temperature": 10},
    {"id": 2, "recordDate": date(2015, 1, 2), "temperature": 25},
    {"id": 3, "recordDate": date(2015, 1, 3), "temperature": 20},
    {"id": 4, "recordDate": date(2015, 1, 4), "temperature": 30},
]
assert solution.risingTemperature(weather1) == [2, 4]  # standard rising days

# Single record
weather2 = [
    {"id": 1, "recordDate": date(2020, 1, 1), "temperature": 15},
]
assert solution.risingTemperature(weather2) == []  # no previous day exists

# Equal temperatures
weather3 = [
    {"id": 1, "recordDate": date(2020, 1, 1), "temperature": 20},
    {"id": 2, "recordDate": date(2020, 1, 2), "temperature": 20},
]
assert solution.risingTemperature(weather3) == []  # must be strictly greater

# Decreasing temperatures
weather4 = [
    {"id": 1, "recordDate": date(2020, 1, 1), "temperature": 30},
    {"id": 2, "recordDate": date(2020, 1, 2), "temperature": 10},
]
assert solution.risingTemperature(weather4) == []  # temperature dropped

# Missing intermediate date
weather5 = [
    {"id": 1, "recordDate": date(2020, 1, 1), "temperature": 10},
    {"id": 2, "recordDate": date(2020, 1, 3), "temperature": 20},
]
assert solution.risingTemperature(weather5) == []  # no record for previous day

# Multiple valid increases
weather6 = [
    {"id": 1, "recordDate": date(2020, 1, 1), "temperature": 5},
    {"id": 2, "recordDate": date(2020, 1, 2), "temperature": 10},
    {"id": 3, "recordDate": date(2020, 1, 3), "temperature": 15},
]
assert solution.risingTemperature(weather6) == [2, 3]  # consecutive increases
Test Why
Basic example Verifies standard rising-temperature behavior
Single record Ensures no comparison occurs without a previous day
Equal temperatures Confirms strict inequality handling
Decreasing temperatures Ensures lower temperatures are excluded
Missing intermediate date Verifies that only adjacent calendar days count
Multiple valid increases Tests repeated successful comparisons

Edge Cases

One important edge case is when the table contains only a single row. Since there is no previous calendar day available for comparison, the result must be empty. A naive implementation that assumes every row has a predecessor could fail or produce invalid comparisons. The implementation handles this correctly by explicitly checking whether yesterday exists before comparing temperatures.

Another important case occurs when dates are missing. For example, if the table contains 2020-01-01 and 2020-01-03, there is no valid comparison for 2020-01-03 because 2020-01-02 is absent. A naive approach that simply compares consecutive rows after sorting would incorrectly treat these dates as adjacent. The implementation avoids this bug by requiring an exact one-day difference.

Equal temperatures are also a subtle edge case. The problem requires temperatures to be strictly higher, not greater than or equal. If yesterday's temperature was 20 and today's temperature is also 20, the row must not be included. The implementation correctly uses the > operator rather than >=.

A final edge case involves unordered input. The rows in the table are not guaranteed to be sorted by date. A naive sequential scan could therefore compare the wrong rows. The hash map approach and the SQL self-join both avoid relying on input order, ensuring correctness regardless of how the records are arranged.