mediumArraysPattern: Basic Traversal
Range Constrained Subsegment Solution
Problem Statement
Given an array of integers 'arr' and a non-negative integer 'limit', determine the length of the longest contiguous subsegment such that the absolute difference between the maximum and minimum element within that subsegment is less than or equal to 'limit'.
Examples
Example 1:
Input:arr = [8, 2, 4, 7], limit = 4
Output:2
Explanation: The subsegments [8], [2], [4], [7], [2, 4], [4, 7] satisfy the condition. The longest is length 2.
Example 2:
Input:arr = [10, 1, 2, 4, 7, 2], limit = 5
Output:4
Explanation: The subsegment [1, 2, 4, 2] has a maximum of 4 and a minimum of 1. The absolute difference is 3, which is <= 5. The length is 4.
Constraints
- 1 <= arr.length <= 10^5
- 0 <= arr[i] <= 10^9
- 0 <= limit <= 10^9
Time: O(n) Space: O(n)
Use a sliding window with two monotonic deques to keep track of the maximum and minimum elements in current window in O(1) amortized time. This reduces the time complexity to O(n) as each element is added and removed from the deques at most once.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from collections import deque
def range_constrained_subsegment(arr, limit):
if not arr:
return 0
max_d, min_d = deque(), deque()
left, max_len = 0, 0
for right in range(len(arr)):
while max_d and arr[max_d[-1]] <= arr[right]:
max_d.pop()
max_d.append(right)
while min_d and arr[min_d[-1]] >= arr[right]:
min_d.pop()
min_d.append(right)
while arr[max_d[0]] - arr[min_d[0]] > limit:
left += 1
if max_d[0] < left:
max_d.popleft()
if min_d[0] < left:
min_d.popleft()
max_len = max(max_len, right - left + 1)
return max_len