Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

This question stacks two ideas. You slide a window, and inside the window you must know both the biggest and the smallest number fast. The interviewer wants to see if you can keep track of both at once while the window moves. Doing that in one pass is the real test here.

🎯 The Problem

You get an array of numbers and a number limit. Here are the rules.

• You want the longest stretch of numbers in a row that follows one rule.
• The biggest number and the smallest number in the stretch must differ by limit or less.
• That difference between the biggest and smallest is the range of the window.
• So the window is valid while its range stays at limit or below.
• Return the length of the longest valid window.

Take the array [8, 2, 4, 7] and limit as 4. The window [2, 4, 7] has biggest 7 and smallest 2, so range 5, which is above 4 and fails. The window [8, 2] has range 6, too big. The window [2, 4] has range 2, fine, length 2. So the longest valid window has length 2.

Input:  nums = [8, 2, 4, 7], limit = 4
Output: 2

Explanation:
[8]       range 0   ok
[8,2]     range 6   too big
[2,4]     range 2   ok   length 2
[2,4,7]   range 5   too big
The longest valid window has length 2.

Here is the idea as a picture. A window covers a stretch of numbers. We track the biggest and the smallest inside. The window is valid while their difference is at most limit.

The window grows while the range fits and shrinks the moment the range gets too big.

🐢 Approach 1: Scan Every Window (Brute Force)

The idea in one line: try every window and scan it from scratch to find its max and min.

The idea:

• Look at every start and every end.
• Scan each window to find the biggest and smallest number.
• The range is biggest minus smallest.

How it works:

• For each window, work out the range.
• If the range is limit or less, the window is valid.
• Track the longest valid window.

Why it is weak:

• There are about n starts and n ends.
• For each pair you scan the window again for max and min.
• That climbs to O(n²) or worse.
• Overlapping windows re-scan the same numbers.

Here is the brute-force code for that idea:

def longest_subarray(nums, limit):
    best = 0
    for left in range(len(nums)):
        smallest = largest = nums[left]
        for right in range(left, len(nums)):
            smallest = min(smallest, nums[right])
            largest = max(largest, nums[right])
            if largest - smallest <= limit:
                best = max(best, right - left + 1)
            else:
                break
    return best

⚡ Approach 2: Two Monotonic Deques (Best)

The idea in one line: keep the window max and the window min ready in two deques, so the range is just the two fronts.

The idea:

• Slide a window with a left and a right pointer.
• The hard part is knowing the max and min of the window fast.
• So keep two monotonic deques. A monotonic deque is a double-ended queue kept in sorted order.
• The max deque keeps biggest at the front. The min deque keeps smallest at the front.

How it works:

• Move right forward and read the new number.
• For the max deque, while the back is smaller than the new number, pop the back. Those can never be the max again.
• For the min deque, while the back is bigger than the new number, pop the back. Those can never be the min again.
• Add the new number to the back of both.
• The range is the max deque front minus the min deque front.
• While that range is above limit, move left forward. If the leaving number equals a deque front, pop that front too.

Why it is fast:

• Each number enters and leaves each deque once.
• No re-scanning for max or min.
• One clean pass, so O(n).

Here is a dry-run on [8, 2, 4, 7] with limit equal to 4. Watch the two deque fronts give the max and min, and watch left jump when the range breaks.

Steps to Solve

1. Make an empty max deque and an empty min deque. Set left to 0 and the best length to 0.
2. Move right from the start to the end of the array.
3. For the max deque, pop the back while its number is smaller than the current number. Then add the current number at the back.
4. For the min deque, pop the back while its number is bigger than the current number. Then add the current number at the back.
5. While the max deque front minus the min deque front is greater than limit, shrink. If the leaving left number equals a deque front, pop that front. Then move left forward.
6. The current window length is right - left + 1. Update the best length.
7. When right reaches the end, the best length is the answer.

#include <stdio.h>

int longestSubarray(int nums[], int n, int limit) {
    int maxd[100000], mind[100000];   // store values
    int mh = 0, mt = 0;   // max deque head and tail
    int nh = 0, nt = 0;   // min deque head and tail
    int left = 0, best = 0;
    for (int right = 0; right < n; right++) {
        int v = nums[right];
        while (mh < mt && maxd[mt - 1] < v) mt--;   // clean max deque back
        maxd[mt++] = v;
        while (nh < nt && mind[nt - 1] > v) nt--;   // clean min deque back
        mind[nt++] = v;
        while (maxd[mh] - mind[nh] > limit) {       // range too big
            if (maxd[mh] == nums[left]) mh++;       // drop from max front
            if (mind[nh] == nums[left]) nh++;       // drop from min front
            left++;                                 // shrink from the left
        }
        int len = right - left + 1;
        if (len > best) best = len;
    }
    return best;
}

int main(void) {
    int nums[] = {8, 2, 4, 7};
    int limit = 4;
    printf("%d\n", longestSubarray(nums, 4, limit));
    return 0;
}

2

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int longestSubarray(vector<int>& nums, int limit) {
    deque<int> maxd, mind;   // store values
    int left = 0, best = 0;
    for (int right = 0; right < (int)nums.size(); right++) {
        int v = nums[right];
        while (!maxd.empty() && maxd.back() < v) maxd.pop_back();  // clean max
        maxd.push_back(v);
        while (!mind.empty() && mind.back() > v) mind.pop_back();  // clean min
        mind.push_back(v);
        while (maxd.front() - mind.front() > limit) {   // range too big
            if (maxd.front() == nums[left]) maxd.pop_front();
            if (mind.front() == nums[left]) mind.pop_front();
            left++;                                     // shrink left
        }
        int len = right - left + 1;
        if (len > best) best = len;
    }
    return best;
}

int main() {
    vector<int> nums = {8, 2, 4, 7};
    int limit = 4;
    cout << longestSubarray(nums, limit) << endl;
    return 0;
}

2

import java.util.ArrayDeque;
import java.util.Deque;

public class LongestSubarray {
    public static int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxd = new ArrayDeque<>();   // window max at front
        Deque<Integer> mind = new ArrayDeque<>();   // window min at front
        int left = 0, best = 0;
        for (int right = 0; right < nums.length; right++) {
            int v = nums[right];
            while (!maxd.isEmpty() && maxd.peekLast() < v) maxd.pollLast();
            maxd.offerLast(v);
            while (!mind.isEmpty() && mind.peekLast() > v) mind.pollLast();
            mind.offerLast(v);
            while (maxd.peekFirst() - mind.peekFirst() > limit) {  // too big
                if (maxd.peekFirst() == nums[left]) maxd.pollFirst();
                if (mind.peekFirst() == nums[left]) mind.pollFirst();
                left++;                                            // shrink
            }
            int len = right - left + 1;
            if (len > best) best = len;
        }
        return best;
    }

    public static void main(String[] args) {
        int[] nums = { 8, 2, 4, 7 };
        int limit = 4;
        System.out.println(longestSubarray(nums, limit));
    }
}

2

from collections import deque


def longest_subarray(nums, limit):
    maxd = deque()       # window max at the front
    mind = deque()       # window min at the front
    left = 0
    best = 0
    for right, v in enumerate(nums):
        while maxd and maxd[-1] < v:
            maxd.pop()              # drop smaller backs from max deque
        maxd.append(v)
        while mind and mind[-1] > v:
            mind.pop()              # drop bigger backs from min deque
        mind.append(v)
        while maxd[0] - mind[0] > limit:    # range too big
            if maxd[0] == nums[left]:
                maxd.popleft()      # the leaving number was the max
            if mind[0] == nums[left]:
                mind.popleft()      # the leaving number was the min
            left += 1               # shrink from the left
        best = max(best, right - left + 1)
    return best


nums = [8, 2, 4, 7]
limit = 4
print(longest_subarray(nums, limit))

2

function longestSubarray(nums, limit) {
  const maxd = []; // window max at the front
  const mind = []; // window min at the front
  let left = 0;
  let best = 0;
  for (let right = 0; right < nums.length; right++) {
    const v = nums[right];
    while (maxd.length && maxd[maxd.length - 1] < v) maxd.pop();
    maxd.push(v);
    while (mind.length && mind[mind.length - 1] > v) mind.pop();
    mind.push(v);
    while (maxd[0] - mind[0] > limit) {   // range too big
      if (maxd[0] === nums[left]) maxd.shift();
      if (mind[0] === nums[left]) mind.shift();
      left++;                             // shrink from the left
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

const nums = [8, 2, 4, 7];
const limit = 4;
console.log(longestSubarray(nums, limit));

2

Let us walk through the Python version line by line and see why each line is there.

The lines maxd = deque() and mind = deque() make the two deques. maxd keeps the window so the biggest number sits at the front. mind keeps the window so the smallest number sits at the front. So at any moment maxd[0] is the window max and mind[0] is the window min.

The lines left = 0 and best = 0 set the left edge of the window and the longest valid length found so far.

The loop for right, v in enumerate(nums) moves the right edge forward. v is the new number entering the window.

The lines while maxd and maxd[-1] < v: maxd.pop() clean the max deque from the back. While the back number is smaller than v, we drop it. Those smaller numbers can never be the maximum while v is in the window. Then maxd.append(v) adds v at the back. This keeps the max deque sorted from biggest at the front to smallest at the back.

The lines while mind and mind[-1] > v: mind.pop() do the mirror for the min deque. While the back number is bigger than v, we drop it. Then mind.append(v) adds v at the back. This keeps the min deque sorted from smallest at the front to biggest at the back.

The loop while maxd[0] - mind[0] > limit checks the range. maxd[0] is the max and mind[0] is the min, so their difference is the range. While the range is too big, the window is invalid, so we shrink.

The lines if maxd[0] == nums[left]: maxd.popleft() and the matching min check handle the leaving number. If the number leaving on the left was the current max, it sits at the front of maxd, so we drop it. Same for the min. Then left += 1 moves the left edge forward.

The line best = max(best, right - left + 1) measures the window. Right after the while loop the window is valid, so its length is a real candidate. We keep the larger of the best so far and this length.

⏱️ Time and Space Complexity

The brute force scans each window for its max and min, so it is slow and repeats work. The two-deque method adds and removes each number from each deque once. So it runs in one pass. That takes the time from O(n²) down to O(n). The two deques together hold at most n numbers, so the extra space is O(n).

🧩 Key Takeaways

• ✅ The window is valid while its range, the max minus the min, stays at limit or below.
• ✅ One monotonic deque keeps the window max at its front, and a second keeps the min at its front.
• ✅ Before adding a new number, drop smaller backs from the max deque and bigger backs from the min deque.
• ✅ When the range breaks the limit, shrink from the left and pop any front that the leaving number owned.
• ✅ Each number enters and leaves each deque once, so the whole scan is O(n) time and O(n) space.

🚀 What’s Next?

• Sliding Window Maximum
• Max Consecutive Ones III