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

medium array sliding window monotonic queue

Problem

Given an array nums and an integer limit, return the length of the longest contiguous subarray such that the absolute difference between any two elements is ≤ limit.

Inputnums = [8,2,4,7], limit = 4

Output2

[2,4] has max-min = 2 ≤ 4. Adding 7 makes diff 5, too big.

nums (comma-separated)

limit

from collections import deque

def longest_subarray(nums, limit):
    mx = deque(); mn = deque(); l = best = 0
    for r, v in enumerate(nums):
        while mx and nums[mx[-1]] <= v: mx.pop()
        while mn and nums[mn[-1]] >= v: mn.pop()
        mx.append(r); mn.append(r)
        while nums[mx[0]] - nums[mn[0]] > limit:
            l += 1
            if mx[0] < l: mx.popleft()
            if mn[0] < l: mn.popleft()
        best = max(best, r - l + 1)
    return best

function longestSubarray(nums, limit) {
  const mx = [], mn = [];
  let l = 0, best = 0;
  for (let r = 0; r < nums.length; r++) {
    while (mx.length && nums[mx[mx.length - 1]] <= nums[r]) mx.pop();
    while (mn.length && nums[mn[mn.length - 1]] >= nums[r]) mn.pop();
    mx.push(r); mn.push(r);
    while (nums[mx[0]] - nums[mn[0]] > limit) {
      l++;
      if (mx[0] < l) mx.shift();
      if (mn[0] < l) mn.shift();
    }
    best = Math.max(best, r - l + 1);
  }
  return best;
}

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> mx = new ArrayDeque<>(), mn = new ArrayDeque<>();
        int l = 0, best = 0;
        for (int r = 0; r < nums.length; r++) {
            while (!mx.isEmpty() && nums[mx.peekLast()] <= nums[r]) mx.pollLast();
            while (!mn.isEmpty() && nums[mn.peekLast()] >= nums[r]) mn.pollLast();
            mx.offerLast(r); mn.offerLast(r);
            while (nums[mx.peekFirst()] - nums[mn.peekFirst()] > limit) {
                l++;
                if (mx.peekFirst() < l) mx.pollFirst();
                if (mn.peekFirst() < l) mn.pollFirst();
            }
            best = Math.max(best, r - l + 1);
        }
        return best;
    }
}

int longestSubarray(vector<int>& nums, int limit) {
    deque<int> mx, mn;
    int l = 0, best = 0;
    for (int r = 0; r < (int)nums.size(); r++) {
        while (!mx.empty() && nums[mx.back()] <= nums[r]) mx.pop_back();
        while (!mn.empty() && nums[mn.back()] >= nums[r]) mn.pop_back();
        mx.push_back(r); mn.push_back(r);
        while (nums[mx.front()] - nums[mn.front()] > limit) {
            l++;
            if (mx.front() < l) mx.pop_front();
            if (mn.front() < l) mn.pop_front();
        }
        best = max(best, r - l + 1);
    }
    return best;
}

Explanation

A window is valid when its biggest number minus its smallest number stays within limit. The hard part is knowing the current max and min quickly as the window slides, without rescanning every element.

The trick is two monotonic deques: mx keeps indices whose values are decreasing (so its front is always the window max), and mn keeps indices whose values are increasing (front is the window min). When a new value arrives, we pop smaller tails from mx and larger tails from mn because they can never beat the newcomer.

We grow the window by moving r right. While nums[mx[0]] - nums[mn[0]] > limit, the window is too wide, so we advance the left edge l and pop any deque front that has fallen out of the window. After fixing it, we update best with the current length r - l + 1.

Example: nums = [8,2,4,7], limit = 4. At [8] max-min is 0. Adding 2 gives diff 6 > 4, so we shrink past 8. The pair [2,4] has diff 2, length 2; adding 7 would make diff 5, too big, so the answer stays 2.

Each index enters and leaves each deque at most once, so the whole scan is linear despite the inner loops.

Time: O(n) Space: O(n)