hardSliding WindowPattern: Monotonic Deque
Max Length Subarray with Bounded Range Solution
Problem Statement
Given an array of integers `values` and an integer `threshold`. Determine the maximum length of a *contiguous subarray* such that the difference between the maximum element and the minimum element within that subarray is less than or equal to `threshold`. Return the length of this longest valid subarray.
Examples
Example 1:
Input:values = [10, 1, 2, 4, 7, 2], threshold = 5
Output:{}
Explanation: The subarray `[2, 4, 7, 2]` has max=7, min=2. Difference = 7 - 2 = 5. Since 5 <= 5, this is a valid subarray of length 4. Subarrays like `[1, 2, 4, 7]` have max=7, min=1, diff=6 > 5, which is invalid. Thus, the maximum length is 4.
Constraints
- 1 <= values.length <= 10^5
- 0 <= values[i] <= 10^9
- 0 <= threshold <= 10^9
Time: O(N) Space: O(N)
An optimized approach uses a sliding window technique with two monotonic deques (one for minimums and one for maximums). The window expands to the right. As elements are added, the deques are updated to maintain their monotonic property and reflect the current window's min/max. If at any point the difference between the maximum (front of max-deque) and minimum (front of min-deque) in the window exceeds `threshold`, the window is shrunk from the left by removing elements until the condition is satisfied again. The maximum valid window length is tracked throughout. This approach ensures O(N) time complexity.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
from collections import deque
def solve(values, threshold):
left = 0
max_length = 0
max_deque = deque() # Stores indices in decreasing order of values
min_deque = deque() # Stores indices in increasing order of values
for right in range(len(values)):
# Maintain max_deque: remove elements smaller than current from back
while max_deque and values[max_deque[-1]] <= values[right]:
max_deque.pop()
max_deque.append(right)
# Maintain min_deque: remove elements larger than current from back
while min_deque and values[min_deque[-1]] >= values[right]:
min_deque.pop()
min_deque.append(right)
# Shrink window from left if invalid (max - min > threshold)
while values[max_deque[0]] - values[min_deque[0]] > threshold:
left += 1
# Remove indices from front of deques if they fall outside the current window [left, right]
if max_deque[0] < left:
max_deque.popleft()
if min_deque[0] < left:
min_deque.popleft()
# Current window [left, right] is valid, update max_length
max_length = max(max_length, right - left + 1)
return max_length
if __name__ == "__main__":
lines = sys.stdin.readlines()
# Read values
values = list(map(int, lines[0].strip().split()))
# Read threshold
threshold = int(lines[1].strip())
result = solve(values, threshold)
print(result)