428. Low-High-Mid Pattern
A trader reviews a list of daily prices in nums looking for a low-high-mid shape: three days i < j < k (in this order, not necessarily next to each other) such that nums[i] < nums[k] < nums[j]. In words, the price on day i is the lowest of the three, day j is the highest, and day k lands strictly between them.
Return true if the list contains at least one such triple and false otherwise. Prices may repeat or be negative, and the comparisons are strict. Lists with fewer than three prices never contain the shape. There can be up to 100,000 prices, so testing every triple (or even every pair) is too slow.
Example 1
- Input:
- nums = [8,20,5,11,2]
- Output:
- true
- Explanation:
Days with prices 8, 20, 11 work: 8 < 11 < 20 in this order, so the answer is true.
Example 2
- Input:
- nums = [9,7,6,8,3,1]
- Output:
- false
- Explanation:
Whenever a higher price follows a lower one (6 then 8, or 7 then 8), every price after it is below that low one, so nothing fits strictly between them.
Constraints
0 ≤ nums.length ≤ 105
-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)