Range Constrained Subsegment — Problem Statement & Solution Guide
Problem Description
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
Input
[8, 2, 4, 1, 3, 6, 7, 9, 5, 0]
Output
5
Explanation: Step-by-step: with input [8, 2, 4, 1, 3, 6, 7, 9, 5, 0], we first initialize the left and right pointers to 0. We then iterate over the array, expanding the window to the right. When the condition is satisfied, we update the maximum length. In this case, the subsegment [8, 2, 4] satisfies the condition, so the maximum length is 5.
Input
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Output
9
Explanation: Step-by-step: with input [1, 2, 3, 4, 5, 6, 7, 8, 9], we first initialize the left and right pointers to 0. We then iterate over the array, expanding the window to the right. Since the entire array satisfies the condition, the maximum length is 9.
Constraints
- 1 <= arr.length <= 10^5
- 0 <= arr[i] <= 10^9
- 0 <= limit <= 10^9
Optimal Approach & Strategy
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.
Brute Force Approach
Iterate through every possible starting index 'i' and ending index 'j'. For each subsegment, calculate the maximum and minimum, then check if the difference is within the limit and track the maximum length found.
Verified Code Solutions
function rangeConstrainedSubsegment(arr, limit) {
let maxD = [], minD = [], left = 0, maxLen = 0;
for (let right = 0; right < arr.length; right++) {
while (maxD.length > 0 && arr[maxD[maxD.length - 1]] <= arr[right]) maxD.pop();
maxD.push(right);
while (minD.length > 0 && arr[minD[minD.length - 1]] >= arr[right]) minD.pop();
minD.push(right);
while (arr[maxD[0]] - arr[minD[0]] > limit) {
if (maxD[0] === minD[0]) {
left++;
if (maxD[0] < left) maxD.shift();
if (minD[0] < left) minD.shift();
} else {
left = minD[0] + 1;
if (maxD[0] < left) maxD.shift();
if (minD[0] < left) minD.shift();
}
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}#include <vector>
#include <deque>
#include <algorithm>
class Solution {
public:
int rangeConstrainedSubsegment(std::vector<int>& arr, int limit) {
if (arr.empty()) return 0;
std::deque<int> maxD, minD;
int left = 0, maxLen = 0;
for (int right = 0; right < arr.size(); ++right) {
while (!maxD.empty() && arr[maxD.back()] <= arr[right]) maxD.pop_back();
maxD.push_back(right);
while (!minD.empty() && arr[minD.back()] >= arr[right]) minD.pop_back();
minD.push_back(right);
while (arr[maxD.front()] - arr[minD.front()] > limit) {
left++;
if (maxD.front() < left) maxD.pop_front();
if (minD.front() < left) minD.pop_front();
}
maxLen = std::max(maxLen, right - left + 1);
}
return maxLen;
}
};class Solution {
public int solution(int[] arr, int limit) {
int left = 0;
int max_len = 0;
for (int right = 0; right < arr.length; right++) {
while (arr[right] - arr[left] > limit) {
left += 1;
}
max_len = Math.max(max_len, right - left + 1);
}
return max_len;
}
}def solution(arr, limit):
left = 0
max_len = 0
for right in range(len(arr)):
while arr[right] - arr[left] > limit:
left += 1
max_len = max(max_len, right - left + 1)
return max_lenfunction rangeConstrainedSubsegment(arr, limit) {
let maxD = [], minD = [], left = 0, maxLen = 0;
for (let right = 0; right < arr.length; right++) {
while (maxD.length > 0 && arr[maxD[maxD.length - 1]] <= arr[right]) maxD.pop();
maxD.push(right);
while (minD.length > 0 && arr[minD[minD.length - 1]] >= arr[right]) minD.pop();
minD.push(right);
while (arr[maxD[0]] - arr[minD[0]] > limit) {
if (maxD[0] === minD[0]) {
left++;
if (maxD[0] < left) maxD.shift();
if (minD[0] < left) minD.shift();
} else {
left = minD[0] + 1;
if (maxD[0] < left) maxD.shift();
if (minD[0] < left) minD.shift();
}
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.