Range Constrained Subsegment — Problem Statement & Solution Guide

ArraysMediumBasic Traversal

TimeO(N)

SpaceO(N)

Quick Answer & Algorithm Key Takeaway

Iterating arrays and tracking min/max

TopicArrays

PatternBasic Traversal

TimeO(N)

SpaceO(N)

Problem Description

You are provided with a sequence of integers, arr, and a non-negative integer threshold, limit. Your task is to identify the maximum length of a contiguous subarray (subsegment) where the spread of values is bounded. Specifically, for any chosen subarray, the difference between its largest element and its smallest element must not exceed limit.

Formally, find the maximum integer L such that there exists a starting index i where the subarray arr[i...i+L-1] satisfies the condition: max(arr[i...i+L-1]) - min(arr[i...i+L-1]) <= limit.

If no such subarray exists (which is impossible given the constraints since a single element always has a spread of 0), return 0. However, since limit is non-negative, a subarray of length 1 is always valid. Return the length of the longest valid subsegment.

DSA Pattern Breakdown

"Range Constrained Subsegment"

medium

WHY DOES IT MATTER?

Maintaining dynamic range constraints while scanning an array is a recurring pattern in real‑time analytics, rate limiting, and windowed statistics. Mastering the monotonic‑deque sliding window equips engineers to solve a broad class of problems where extremal values must be queried efficiently over moving intervals.

OPTIMIZATION CHALLENGE

The key insight is that the global minimum and maximum of a sliding window can be maintained without recomputation by discarding elements that can never become the new extreme. This monotonic property reduces the naive quadratic recomputation to linear time.

REAL-WORLD CONNECTION

Think of a network traffic monitor that must alert when the latency variation within the last K seconds exceeds a threshold. The monitor slides a time window over incoming latency samples, constantly updating the min and max latency using deques, just like the algorithm does for array indices.

When coding, keep the deques storing indices, not values, so you can easily verify whether the front element has fallen out of the current window (i.e., its index < left pointer). This tiny detail prevents subtle bugs and keeps the algorithm O(N).

COMPLEXITY AT A GLANCE

⏱ Time:O(N)

💾 Space:O(N)

Core Theory — Why This Approach?

The problem asks for the longest contiguous subarray whose maximum and minimum values differ by at most limit. A naïve solution would recompute the min and max for every possible window, leading to O(N²) time, which is infeasible for N up to 10⁵ or more. The optimal paradigm is a sliding‑window (two‑pointer) technique combined with monotonic deques that keep track of the current window’s minimum and maximum in O(1) amortized time. Each element is pushed and popped at most once from each deque, guaranteeing linear overall complexity.

The monotonic deque works by storing indices in decreasing order for the maximum deque and increasing order for the minimum deque. When the right pointer expands, we purge elements from the back that are smaller (for max) or larger (for min) than the incoming value, preserving the monotonic property. The front of each deque always holds the index of the current window’s extreme value. If the spread exceeds limit, we shrink the left side of the window, discarding indices that fall out of range. This dynamic adjustment yields the longest feasible window while maintaining O(N) time and O(N) worst‑case space (actually O(limit) but bounded by N).

Interview Questions on This Problem

Q1How would you modify the solution if the constraint was that the sum of the subarray must not exceed `limit` instead of the value spread?

Use a classic sliding window where we maintain a running sum. Expand the right pointer, add arr[right] to the sum, and while sum > limit, shrink from the left, subtracting arr[left]. The window size at each step gives the longest subarray with sum ≤ limit, achieving O(N) time and O(1) extra space.

Q2Can the algorithm be adapted to work with a stream of numbers where the total length is unknown in advance?

Yes. The two‑pointer window becomes a sliding buffer over the stream. As each new element arrives, we update the deques and possibly advance the left pointer, discarding stale indices. Since each element is processed once, the approach remains O(1) amortized per element and uses O(K) space where K is the current window size.

Q3What is the time‑space trade‑off if we replace the deques with a balanced binary search tree (e.g., multiset) to track min and max?

A balanced BST allows O(log N) insertion, deletion, and retrieval of min/max, leading to O(N log N) overall time, which is slower than the O(N) deque solution. However, it simplifies handling duplicate values and arbitrary removal, and the space remains O(N). The deque approach is preferred when only min and max are needed.

Examples

Example 1

Input

arr = [8, 2, 4, 7, 5], limit = 4

Output

Explanation: Consider the subarray [2, 4, 7]. The maximum is 7 and the minimum is 2. The difference is 7 - 2 = 5, which is greater than 4, so this is invalid. Consider [4, 7, 5]. Max is 7, min is 4. Difference is 3, which is <= 4. Length is 3. Consider [2, 4]. Max 4, min 2, diff 2 <= 4. Length 2. Consider [8, 2]. Max 8, min 2, diff 6 > 4. The longest valid subsegment is [4, 7, 5] or [2, 4, 7] is invalid, wait. Let's re-evaluate. [2,4] diff 2. [4,7] diff 3. [7,5] diff 2. [2,4,7] diff 5 (invalid). [4,7,5] diff 3 (valid, len 3). [8,2] diff 6 (invalid). [2,4,7,5] max 7 min 2 diff 5 (invalid). So max length is 3.

Example 2

Input

arr = [1, 5, 2, 6, 3], limit = 2

Output

Explanation: Check subarrays of length 3: [1,5,2] max 5 min 1 diff 4 > 2. [5,2,6] max 6 min 2 diff 4 > 2. [2,6,3] max 6 min 2 diff 4 > 2. Check subarrays of length 2: [1,5] diff 4 > 2. [5,2] diff 3 > 2. [2,6] diff 4 > 2. [6,3] diff 3 > 2. Check subarrays of length 1: All have diff 0 <= 2. Wait, let's re-check [5,2]. 5-2=3. [2,6]. 6-2=4. [6,3]. 6-3=3. [1,5]. 5-1=4. It seems no length 2 subarray works? Let's check [5,2] again. No. What about [2,6]? No. Is there a length 2? [1,5] no. [5,2] no. [2,6] no. [6,3] no. So max length is 1? Let's re-read the example. Ah, I need to ensure the example is correct. Let's pick a better example. Revised Example 2: arr = [1, 3, 2, 5, 4], limit = 2 [1,3] diff 2 (ok). [3,2] diff 1 (ok). [2,5] diff 3 (no). [5,4] diff 1 (ok). [1,3,2] max 3 min 1 diff 2 (ok, len 3). [3,2,5] max 5 min 2 diff 3 (no). [2,5,4] max 5 min 2 diff 3 (no). So max length is 3.

Example 3

Input

arr = [10, 10, 10, 10], limit = 0

Output

Explanation: All elements are identical. For any subarray, max = min = 10. The difference is 0, which is <= 0. Therefore, the entire array is a valid subsegment. The length is 4.

Constraints

1 <= arr.length <= 10^5
-10^9 <= arr[i] <= 10^9
0 <= limit <= 10^9

Optimal Approach & Strategy

Apply a sliding window with two monotonic deques to maintain the current window's minimum and maximum in O(1) amortized time, adjusting the left pointer whenever the spread exceeds the limit. This yields O(N) time and O(N) space.

Brute Force Approach

Check every possible subarray, compute its min and max, and keep the longest that satisfies max‑min ≤ limit. This requires O(N³) time if min/max are recomputed each time, or O(N²) with pre‑computed prefix minima, still too slow for large N.

Code Solutions

Language:

JavaScript Solution

Time: O(N)

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_len

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;
}

Asked in Top Tech Interviews

TCS

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.