The naive approach involves checking every possible subarray to see if it satisfies the condition and then tracking the maximum length found.

1. Iterate through the array with a starting pointer i from 0 to n-1.
2. Iterate with an ending pointer j from i to n-1.
3. For each subarray defined by nums[i...j], scan the elements to find the minimum and maximum values.
4. Calculate the absolute difference. If it is $\le$ limit, update the maximum length.

python
# Pseudo-code for Brute Force
def longestSubarray(nums, limit):
    max_len = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            # Scan subarray to find min and max
            current_min = min(nums[i:j+1])
            current_max = max(nums[i:j+1])
            
            if current_max - current_min <= limit:
                max_len = max(max_len, j - i + 1)
    return max_len

Time Complexity Analysis: The time complexity is $O(N^3)$. There are $O(N^2)$ subarrays, and finding the min/max for each takes $O(N)$. Even if optimized to update min/max incrementally ($O(N^2)$ total), this approach fails because $N$ can be up to $10^5$. An $O(N^2)$ solution would perform roughly $10^{10}$ operations, resulting in a Time Limit Exceeded (TLE) error.

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

The primary challenge in LeetCode 1438 is efficiently checking the condition max - min <= limit as the window slides.

In a standard sliding window, adding an element is cheap. However, determining the new maximum or minimum of the current window usually requires scanning the window ($O(K)$) or using a heap/balanced tree ($O(\log K)$). To achieve the optimal $O(N)$ solution, we need to query the min and max in $O(1)$ time.

The core insight is to maintain two Monotonic Deques (Double-Ended Queues):

1. Decreasing Deque: Stores indices of potential maximums. The front of the deque always holds the index of the maximum element in the current window.
2. Increasing Deque: Stores indices of potential minimums. The front of the deque always holds the index of the minimum element in the current window.

Visual Description: Imagine the window expanding to the right. When a new number enters:

• If it is larger than the numbers currently at the back of the "max deque," those smaller numbers can never be the maximum again (since the new number is larger and to their right). We pop them.
• If it is smaller than the numbers at the back of the "min deque," those larger numbers can never be the minimum again. We pop them.
• The new number is added to the back.

This ensures the elements in the deques are always sorted. The front of the "max deque" is the window's max, and the front of the "min deque" is the window's min. If nums[max_deque.front()] - nums[min_deque.front()] > limit, we shrink the window from the left and remove indices from the front of the deques if they fall out of bounds.

Execution Flow

Let's trace the algorithm with nums = [8, 2, 4, 7], limit = 4.

1. Init: left = 0, res = 0, maxD = [], minD = [].
2. i = 0, num = 8:
   • maxD: Push 0. [0] (val 8).
   • minD: Push 0. [0] (val 8).
   • Diff: $|8 - 8| = 0 \le 4$. Valid.
   • res = 1.
3. i = 1, num = 2:
   • maxD: 2 < 8, push 1. [0, 1] (vals 8, 2).
   • minD: 2 < 8, pop 0. Push 1. [1] (val 2).
   • Diff: nums[0] (8) - nums[1] (2) = 6 > 4. Invalid.
   • Shrink: Increment left to 1.
   • maxD: Front is 0. $0 < 1$, so pop front. maxD is [1] (val 2).
   • minD: Front is 1. , keep.
4. i = 2, num = 4:
   • maxD: 4 > 2, pop 1. Push 2. [2] (val 4).
   • minD: 4 > 2, push 2. [1, 2] (vals 2, 4).
   • Diff: $|4 - 2| = 2 \le 4$. Valid.
   • res = max(1, 2) = 2.
5. i = 3, num = 7:
   • maxD: 7 > 4, pop 2. Push 3. [3] (val 7).
   • minD: 7 > 4, push 3. [1, 2, 3] (vals 2, 4, 7).
   • Diff: $|7 - 2| = 5 > 4$. Invalid.
   • Shrink: Increment left to 2.
   • maxD: Front 3 2. Keep.

Final Result: 2.

Proof of Correctness

The algorithm guarantees correctness because it exhaustively checks every possible ending position (right) of a valid subarray. For each right, the left pointer is adjusted to the minimum possible index such that the window [left, right] satisfies the condition. Since the window expands greedily and shrinks only when necessary (monotonicity of the problem), we never miss a valid window larger than the current maximum. The monotonic deques ensure that we always have the correct minimum and maximum of the current window range in $O(1)$ time.

Reference Implementation

C++ Solution for LeetCode 1438

cpp
#include <vector>
#include <deque>
#include <algorithm>

class Solution {
public:
    int longestSubarray(std::vector<int>& nums, int limit) {
        std::deque<int> maxD; // Stores indices, values decreasing
        std::deque<int> minD; // Stores indices, values increasing
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < nums.size(); ++right) {
            // Maintain decreasing order for maxD
            while (!maxD.empty() && nums[maxD.back()] <= nums[right]) {
                maxD.pop_back();
            }
            maxD.push_back(right);

            // Maintain increasing order for minD
            while (!minD.empty() && nums[minD.back()] >= nums[right]) {
                minD.pop_back();
            }
            minD.push_back(right);

            // Check if current window exceeds limit
            while (nums[maxD.front()] - nums[minD.front()] > limit) {
                left++;
                // Remove indices that are now out of the window
                if (maxD.front() < left) maxD.pop_front();
                if (minD.front() < left) minD.pop_front();
            }

            maxLength = std::max(maxLength, right - left + 1);
        }

        return maxLength;
    }
};

Java Solution for LeetCode 1438

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

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxD = new ArrayDeque<>(); // Indices, decreasing values
        Deque<Integer> minD = new ArrayDeque<>(); // Indices, increasing values
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < nums.length; right++) {
            // Maintain decreasing order for maxD
            while (!maxD.isEmpty() && nums[maxD.peekLast()] <= nums[right]) {
                maxD.pollLast();
            }
            maxD.offerLast(right);

            // Maintain increasing order for minD
            while (!minD.isEmpty() && nums[minD.peekLast()] >= nums[right]) {
                minD.pollLast();
            }
            minD.offerLast(right);

            // Shrink window if limit is violated
            while (nums[maxD.peekFirst()] - nums[minD.peekFirst()] > limit) {
                left++;
                // Remove indices that fell out of the window
                if (maxD.peekFirst() < left) {
                    maxD.pollFirst();
                }
                if (minD.peekFirst() < left) {
                    minD.pollFirst();
                }
            }

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

        return maxLength;
    }
}

Python Solution for LeetCode 1438

python
from collections import deque

class Solution:
    def longestSubarray(self, nums: list[int], limit: int) -> int:
        max_d = deque() # Indices, decreasing values
        min_d = deque() # Indices, increasing values
        left = 0
        max_len = 0
        
        for right in range(len(nums)):
            # Maintain decreasing order for max_d
            while max_d and nums[max_d[-1]] <= nums[right]:
                max_d.pop()
            max_d.append(right)
            
            # Maintain increasing order for min_d
            while min_d and nums[min_d[-1]] >= nums[right]:
                min_d.pop()
            min_d.append(right)
            
            # Check condition: max - min <= limit
            while nums[max_d[0]] - nums[min_d[0]] > limit:
                left += 1
                # If the max or min index is now outside the window, remove it
                if max_d[0] < left:
                    max_d.popleft()
                if min_d[0] < left:
                    min_d.popleft()
            
            max_len = max(max_len, right - left + 1)
            
        return max_len