Longest Continuous Subarray With Absolute Diff at Most Limit: Monotonic Deque Pattern

LeetCode 1438 Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit asks you to find the longest subarray where the difference between the largest and smallest element is at most limit. You are given an integer array nums and an integer limit, and you need to return the size of the longest such subarray.

The problem

Given nums and an integer limit, return the length of the longest contiguous subarray such that the absolute difference between any two elements in the subarray is less than or equal to limit.

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

The subarray [2, 4] has max 4 and min 2. The difference is 2, which is within the limit. No longer subarray satisfies the constraint.

Why brute force is too slow

The brute force checks every subarray and computes the min and max:

def longest_subarray_brute(nums, limit):
    n = len(nums)
    best = 0
    for i in range(n):
        for j in range(i, n):
            window = nums[i:j + 1]
            if max(window) - min(window) <= limit:
                best = max(best, j - i + 1)
            else:
                break
    return best

This runs in O(n^2) time. For large arrays (up to 100,000 elements), it will time out. The problem is that for every new subarray boundary, you recompute the min and max from scratch instead of updating them incrementally.

What you really want is a way to track the max and min of the current window as elements enter and leave, with O(1) updates per step.

The approach: sliding window with two monotonic deques

The key insight is that the "absolute difference between any two elements" in a subarray is just max(subarray) - min(subarray). If you can track the running max and running min efficiently, you can check the constraint in O(1).

You maintain two deques:

1. maxDeque: stores indices in decreasing order of their values. The front is always the index of the current window maximum.
2. minDeque: stores indices in increasing order of their values. The front is always the index of the current window minimum.

The algorithm:

1. Expand right one position at a time.
2. Update both deques: pop elements from the back of maxDeque that are smaller than the new element, and pop elements from the back of minDeque that are larger than the new element.
3. Check if nums[maxDeque[0]] - nums[minDeque[0]] > limit. If so, shrink from the left by advancing left. Remove deque fronts if they fall outside the window.
4. Record the best window size.

The solution

from collections import deque

def longest_subarray(nums, limit):
    max_dq = deque()
    min_dq = deque()
    left = 0
    best = 0

    for right in range(len(nums)):
        while max_dq and nums[max_dq[-1]] <= nums[right]:
            max_dq.pop()
        max_dq.append(right)

        while min_dq and nums[min_dq[-1]] >= nums[right]:
            min_dq.pop()
        min_dq.append(right)

        while nums[max_dq[0]] - nums[min_dq[0]] > limit:
            left += 1
            if max_dq[0] < left:
                max_dq.popleft()
            if min_dq[0] < left:
                min_dq.popleft()

        best = max(best, right - left + 1)

    return best

Let's walk through how each piece works.

The outer loop advances right through every index. For each new element, we first maintain the maxDeque: we pop all indices from the back whose values are less than or equal to nums[right], because those elements can never be the maximum for any future window that includes right. Then we push right. The front of maxDeque is always the index of the current maximum.

We do the mirror operation for minDeque: pop all indices from the back whose values are greater than or equal to nums[right], then push right. The front of minDeque is always the index of the current minimum.

After updating both deques, we check the constraint. If nums[max_dq[0]] - nums[min_dq[0]] exceeds the limit, the window is invalid. We advance left and clean up any deque fronts that have fallen out of the window. We keep shrinking until the constraint holds.

Finally, we record the best window size.

Step-by-step walkthrough

Let's trace through nums = [8, 2, 4, 7] with limit = 4. Watch how the two deques maintain the window max and min as elements enter and leave.

A few things to notice:

• The maxDeque is always decreasing and the minDeque is always increasing. This is what makes lookup of the current max and min O(1): just peek at the front.
• Step 2 is where the first shrink happens. Adding 2 creates a window [8, 2] with diff 6. Since 6 exceeds the limit, we must move left past index 0.
• Each index is pushed once and popped at most once from each deque. Across the entire run, total operations on both deques are O(n).

Complexity analysis

Time: O(n). Each element is pushed onto each deque once and popped at most once. The left pointer advances at most n times total. All operations per element are amortized O(1).

Space: O(n). In the worst case (a sorted array with a large limit), both deques could hold all n elements. Typically the deques stay much smaller.

The building blocks

1. Monotonic deque for running max

The decreasing deque pattern for tracking the maximum:

while max_dq and nums[max_dq[-1]] <= nums[right]:
    max_dq.pop()
max_dq.append(right)

When a new element arrives, pop everything smaller from the back. Those elements are now irrelevant because the new element is both larger and further right. The front of the deque is always the window max. This is the same pattern from Sliding Window Maximum, and it appears any time you need a running max over a dynamic window.

2. Monotonic deque for running min

The increasing deque pattern for tracking the minimum:

while min_dq and nums[min_dq[-1]] >= nums[right]:
    min_dq.pop()
min_dq.append(right)

This is the mirror image. Pop everything larger from the back, because those elements can never be the minimum for any future window. The front is always the window min. By combining this with the max deque, you can track the full range of values in the window and check any range-based constraint in O(1).

Edge cases

Before submitting, verify your solution handles these:

• All elements the same like [5, 5, 5, 5] with any limit. The diff is always 0, so the answer is the entire array length.
• Limit is 0. Only windows of identical consecutive elements are valid. The answer is the longest run of equal values.
• Strictly increasing or decreasing array. The window shrinks aggressively whenever the range exceeds the limit. Both deques stay small.
• Single element nums = [42]. The answer is always 1 regardless of the limit.
• Very large limit that exceeds the global range. The entire array is one valid window. Return n.

The two-deque approach handles all of these without special-case branching.

From understanding to recall

You have walked through the two-deque sliding window for tracking min and max simultaneously. You understand why each deque maintains its monotonic invariant and why the total work is O(n). But could you write this from scratch under time pressure?

The tricky details are all in the deque maintenance. Do you pop with <= or < for the max deque? Do you clean up the front before or after advancing left? Do you check max_dq[0] < left or max_dq[0] <= left? These details are where recall fails, and they are exactly what spaced repetition is designed to lock in.

You practice writing both deques and the shrink loop from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "subarray, max minus min, limit" in a problem, and the two-deque template flows without hesitation.

Related posts

• Sliding Window Maximum - The classic single-deque problem. This problem extends that idea by adding a second deque for the minimum.
• Longest Repeating Character Replacement - Another variable-size sliding window with a different validity condition, great for contrasting window strategies.
• Grumpy Bookstore Owner - A fixed-size sliding window problem that shows the other flavor of window-based optimization.

CodeBricks breaks the two-deque sliding window into its reusable pieces and drills them independently. You type the max-deque pop loop, the min-deque pop loop, and the shrink condition from scratch each time, building the muscle memory so that when a range-constrained subarray problem appears in your interview, you write the solution without hesitation.