415. Bounded Window Count
A weather station records one temperature reading per hour in the array nums. A report is built from a window, which is a non-empty run of consecutive hours. A window is called exact when its coldest reading equals minK and its hottest reading equals maxK, with both values really occurring in the window.
Count how many exact windows exist. Windows are different when their start or end hours differ, even if they contain the same numbers. The count can be larger than a 32-bit integer, so it is returned as a 64-bit integer.
Example 1
- Input:
- nums = [1,3,5,2,7,5], minK = 1, maxK = 5
- Output:
- 2
- Explanation:
Exact windows must lie inside the values 1 to 5 and contain both a 1 and a 5, so the 7 cannot be included. The windows are
[1,3,5]and[1,3,5,2], so the count is 2.
Example 2
- Input:
- nums = [4,4,4], minK = 4, maxK = 4
- Output:
- 6
- Explanation:
Every non-empty window of equal values 4 has minimum and maximum 4: three windows of length 1, two of length 2 and one of length 3, in total 6.
Example 3
- Input:
- nums = [2,9,3], minK = 2, maxK = 3
- Output:
- 0
- Explanation:
The 9 is above the allowed range and splits the array, and the remaining pieces never contain both a 2 and a 3 together, so the answer is 0.
Constraints
1 ≤ nums.length ≤ 105
1 ≤ nums[i], minK, maxK ≤ 106
minK ≤ maxK
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 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)