Longest Continuous Subarray With…

1. Define the problem

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

Return the size of the longest contiguous subarray where max − min is at most limit . Maintain two monotonic deques for the window max and min; grow right, and shrink left whenever the absolute difference exceeds the limit.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums_i ≤ 10⁹
0 ≤ limit ≤ 10⁹

Example

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

Output2

Explanation [2, 4] and [4, 7] are valid length-2 windows; any length-3 window exceeds the limit.

2. Know the words first

In plain terms

Absolute difference: The gap between two numbers, ignoring which one is bigger — the absolute difference between 8 and 2 is 6, same as between 2 and 8.

3. Visualize the solution

Deque max/min keep abs diff in range

Statusvalid

Single element; max − min = 0; best = 1.

What happens in this step

window = [0, 0]  [8]

maxDeque front = 8, minDeque front = 8

max − min = 8 − 8 = 0 ≤ limit(4) — valid; best = 1.

Step 1 of 5

Steps to visualize

Grow right and push the index into both a decreasing max deque and increasing min deque.
Window max and min sit at the fronts of those deques.
While max − min exceeds the limit, advance left and drop expired deque fronts.
After each fix, update best with the current window length.
Continue until right reaches the end of the array.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Deque max/min keep abs diff in range

Statusvalid

Single element; max − min = 0; best = 1.

What happens in this step

window = [0, 0]  [8]

maxDeque front = 8, minDeque front = 8

max − min = 8 − 8 = 0 ≤ limit(4) — valid; best = 1.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function longestSubarray(nums, limit) {
  const maxDeque = [];
  const minDeque = [];
  let left = 0;
  let best = 0;

  for (let right = 0; right < nums.length; right++) {
    while (maxDeque.length && nums[maxDeque[maxDeque.length - 1]] <= nums[right]) {
      maxDeque.pop();
    }
    maxDeque.push(right);

    while (minDeque.length && nums[minDeque[minDeque.length - 1]] >= nums[right]) {
      minDeque.pop();
    }
    minDeque.push(right);

    while (nums[maxDeque[0]] - nums[minDeque[0]] > limit) {
      if (maxDeque[0] === left) maxDeque.shift();
      if (minDeque[0] === left) minDeque.shift();
      left++;
    }

    best = Math.max(best, right - left + 1);
  }

  return best;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`nums = [8, 2, 4, 7], limit = 4`	`2`	Docstring example
`nums = [5], limit = 0`	`1`	Single element
`nums = [1, 2, 3], limit = 100`	`3`	Entire array fits the limit
`nums = [4, 4, 4, 5, 4], limit = 0`	`3`	limit 0 requires identical values
`nums = [2, 2, 2, 2], limit = 0`	`4`	All identical with limit 0
`nums = [10, 1, 2, 4, 7, 2], limit = 5`	`4`	Classic second LeetCode example
`nums = [4, 2, 2, 2, 4, 4, 2, 2], limit = 0`	`3`	Longest identical run length 3

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