# High Water Mark > Even below zero, one reading still stands above the rest. Canonical URL: Domain: Python · Difficulty: easy · Seniority: L3 ## Problem A weather station logs each hour's temperature into a non-empty list of integers, and on cold nights every reading can sit below zero. For each hour, return the highest temperature recorded up to and including that hour. ## Example 1 Input: ``` readings = [12,5,19,7,3] ``` Output: ``` [12,12,19,19,19] ``` ## Example 2 Input: ``` readings = [-8,-3,-11,-5] ``` Output: ``` [-8,-3,-3,-3] ``` ## Worked solution and explanation ### Not the max. The max so far. This looks like 'find the biggest number' and it is not. You are asked for the high-water-mark at every hour, so a single `max()` call is useless here: it hands back one scalar when you need the best-so-far at each position. The only way there is to carry a running maximum forward as you walk the list. Here is the part that bites people: that running max has to start from the first reading, not 0. Seed it at 0 because the sunny examples are all positive, and on a cold night your early hours report 0, a temperature that was never on the log. On [-8, -3, -11, -5] a 0-seeded scan emits [0, 0, 0, 0] instead of [-8, -3, -3, -3]. --- ### How to get there #### Step 1: Seed from the data, not from a guess Set the running high to `readings[0]` and make it the first entry of your result. It is a real value from the data, so it can never sit above every actual reading the way 0 does on a cold night. This is the one decision the problem is really testing. #### Step 2: Scan and record each hour Walk the remaining readings once. Replace the running high whenever a reading beats it, then record the current high for that hour. One comparison and one append per element, nothing kept around but the best-so-far. --- ### The solution **Single pass, best-so-far seeded from the first reading** ```python def high_water_marks(readings): high = readings[0] marks = [high] for reading in readings[1:]: if reading > high: high = reading marks.append(high) return marks ``` > **One pass beats re-maxing every prefix** > > **O(n) time**, where n is the number of readings: each one is compared once and recorded once. Space is O(n) for the result list plus O(1) working state. The tempting O(n^2) version calls `max(readings[:i+1])` at every hour, rescanning the whole prefix each time; carrying the running high avoids all of that. > **Where you seed the high is the tell** > > Where the running high is initialized. Seeding from `readings[0]` (a value the data actually contains) instead of 0 or `-float('inf')` is the tell that you reasoned about the negative case before it bit you. The second tell is that you did it in one pass instead of re-maxing each prefix. > **A zero seed invents temperatures** > > Initializing the running high to 0. On a cold night like [-5, -3, -1] every early hour reports 0, a temperature that was never recorded, because 0 outranks every negative reading until a larger one arrives. The friendly positive examples hide this completely. --- ## Common follow-up questions - The station could send an empty log during an outage. What comes back then? _(Tests whether you add a guard clause and define a sensible return value for empty input.)_ - Now readings stream in one at a time and you cannot keep the full list in memory. How does your approach change? _(Tests carrying O(1) state between calls instead of holding the whole history.)_ - Instead of every hour's high-water-mark, return only the hours where a new record was set. How? _(Tests detecting strict improvements and filtering the output down to record-setting hours.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/high_water_mark) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.