Increasing Triplet Subsequence
Real-world version: Three Rising Gauge MarksThe statement here is our own: the same inputs, outputs and technique.
A river gauge writes one reading per hour into a log. readings[t] is the water level at hour t, measured against the datum mark, so it may be negative when the level sits below the mark.
The flood office wants to know whether the log contains a rising trio: three hours i < j < k with readings[i] < readings[j] < readings[k]. The three hours do not have to be next to each other, but they must appear in that order in the log, and each step must be a strict increase.
Return true if the log contains a rising trio and false otherwise. Your solution should run in O(n) time and use O(1) extra space.
Examples
Example 1
- Input
- readings = [9, 4, -2, 5, 1, 7]
- Output
- true
Hours 2, 3 and 5 hold -2, 5 and 7. Those hours are in increasing order and -2 < 5 < 7, so the log has a rising trio.
Example 2
- Input
- readings = [8, 8, 3, 3, -1, -1]
- Output
- false
No reading is ever followed later by a larger one, so not even a rising pair exists, let alone a trio.
Example 3
- Input
- readings = [6, 1, 7, 2, 8]
- Output
- true
Hours 1, 3 and 4 hold 1, 2 and 8, and 1 < 2 < 8.
Example 4
- Input
- readings = [4, 5, 1, 2]
- Output
- false
The rising pairs available are (4, 5) and (1, 2), and neither has a third larger reading after it, so there is no trio.
Example 5
- Input
- readings = [5, 5, 5, 5]
- Output
- false
Every reading equals the next, and equal readings are not a strict increase.
Constraints
- 1 <= readings.length <= 5 * 10^5
- -2^31 <= readings[i] <= 2^31 - 1
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def has_rising_trio(readings: list[int]) -> bool:public boolean hasRisingTrio(int[] readings)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 passed
- Passed: 5 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's