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

The problem asks us to find the length of the longest contiguous subarray in an integer array nums such that the absolut

leetcodemediumarrayqueuesliding-windowheap-(priority-queue)ordered-setmonotonic-queue

LeetCode Problem 1438

Difficulty: 🟡 Medium
Topics: Array, Queue, Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue

Solution

Problem Understanding

The problem asks us to find the length of the longest contiguous subarray in an integer array nums such that the absolute difference between any two elements in that subarray does not exceed a given limit. In other words, for any valid subarray, if max_val is the maximum element and min_val is the minimum element, then max_val - min_val <= limit.

The input consists of an array of integers nums and an integer limit. The output is a single integer representing the maximum length of a subarray that satisfies the absolute difference condition.

The constraints are important because they indicate that a naive solution that examines all possible subarrays will be too slow. Specifically, nums.length can be up to 10^5, so any solution with O(n²) time complexity will not finish within reasonable time limits. The element values and the limit can also be very large (up to 10^9), which means we cannot rely on counting sorts or other tricks that depend on small integer ranges.

Important edge cases include arrays with all identical elements, arrays where limit is zero, and arrays with strictly increasing or decreasing elements. These scenarios test whether the algorithm correctly handles situations where the minimum or maximum changes frequently.

Approaches

The brute-force approach would examine every possible subarray, compute the minimum and maximum in that subarray, and check if the difference is within limit. This guarantees correctness because it literally checks every possibility, but it is too slow with a time complexity of O(n²) or worse, which is infeasible for n = 10^5.

The key insight for an optimal solution is that we can maintain a sliding window that satisfies the absolute difference condition. To do this efficiently, we need to quickly determine the minimum and maximum values in the current window. Using monotonic queues (double-ended queues that maintain elements in increasing or decreasing order) allows us to do this in O(1) time per operation while moving the window. By adjusting the left boundary whenever the difference exceeds limit, we can expand and shrink the window dynamically and find the maximum length in O(n) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every subarray and computes min and max each time
Optimal (Sliding Window + Monotonic Queue) O(n) O(n) Uses two monotonic queues to track min and max values efficiently

Algorithm Walkthrough

  1. Initialize two double-ended queues minDeque and maxDeque. minDeque will keep elements in increasing order to track the minimum, and maxDeque will keep elements in decreasing order to track the maximum.
  2. Initialize two pointers left = 0 and right = 0 to represent the sliding window, and a variable maxLength = 0.
  3. Iterate right from 0 to the end of nums:

a. Add nums[right] to minDeque by removing elements from the end that are greater than nums[right]. This maintains the increasing order.

b. Add nums[right] to maxDeque by removing elements from the end that are smaller than nums[right]. This maintains the decreasing order. 4. Check if the difference between the first elements of maxDeque and minDeque exceeds limit. If so, move left forward to shrink the window:

a. If nums[left] is equal to the first element of minDeque, pop it from minDeque.

b. If nums[left] is equal to the first element of maxDeque, pop it from maxDeque.

c. Increment left by 1. 5. After adjusting left, update maxLength to the maximum of its current value and right - left + 1. 6. Return maxLength after the loop completes.

The algorithm works because the sliding window invariant guarantees that the maximum and minimum in the window always satisfy max - min <= limit. When the invariant is violated, the window is shrunk from the left until it is restored.

Python Solution

from collections import deque
from typing import List

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        minDeque = deque()
        maxDeque = deque()
        left = 0
        maxLength = 0

        for right, num in enumerate(nums):
            while minDeque and num < minDeque[-1]:
                minDeque.pop()
            minDeque.append(num)

            while maxDeque and num > maxDeque[-1]:
                maxDeque.pop()
            maxDeque.append(num)

            while maxDeque[0] - minDeque[0] > limit:
                if nums[left] == minDeque[0]:
                    minDeque.popleft()
                if nums[left] == maxDeque[0]:
                    maxDeque.popleft()
                left += 1

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

        return maxLength

The Python implementation uses deque for the monotonic queues. Each iteration updates the queues by maintaining their order, ensuring O(1) amortized operations per element. The while loop inside the main loop adjusts the left boundary only when the limit is violated.

Go Solution

package main

func longestSubarray(nums []int, limit int) int {
    minDeque := []int{}
    maxDeque := []int{}
    left, maxLength := 0, 0

    for right, num := range nums {
        for len(minDeque) > 0 && num < minDeque[len(minDeque)-1] {
            minDeque = minDeque[:len(minDeque)-1]
        }
        minDeque = append(minDeque, num)

        for len(maxDeque) > 0 && num > maxDeque[len(maxDeque)-1] {
            maxDeque = maxDeque[:len(maxDeque)-1]
        }
        maxDeque = append(maxDeque, num)

        for maxDeque[0] - minDeque[0] > limit {
            if nums[left] == minDeque[0] {
                minDeque = minDeque[1:]
            }
            if nums[left] == maxDeque[0] {
                maxDeque = maxDeque[1:]
            }
            left++
        }

        if right-left+1 > maxLength {
            maxLength = right - left + 1
        }
    }

    return maxLength
}

In Go, slices are used for the monotonic queues. The append and slice operations simulate the deque behavior. Go requires explicit slice management, but the logic mirrors the Python implementation closely.

Worked Examples

Example 1: nums = [8,2,4,7], limit = 4

Right num minDeque maxDeque Left maxLength
0 8 [8] [8] 0 1
1 2 [2] [8,2] 0 → 1 1
2 4 [2,4] [8,4] 1 → 2 2
3 7 [4,7] [7] 2 → 3 2

Final output is 2.

Example 2: nums = [10,1,2,4,7,2], limit = 5

Right num minDeque maxDeque Left maxLength
0 10 [10] [10] 0 1
1 1 [1] [10,1] 0 → 1 1
2 2 [1,2] [10,2] 1 2
3 4 [1,2,4] [10,4] 1 3
4 7 [1,4,7] [10,7] 2 4
5 2 [2,7] [7,2] 2 → 3 4

Final output is 4.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is pushed and popped from the deque at most once, leading to linear time
Space O(n) In the worst case, the deques store all elements of nums

The sliding window combined with monotonic queues ensures linear traversal while maintaining min and max efficiently, avoiding nested loops.

Test Cases

# Provided examples
assert Solution().longestSubarray([8,2,4,7], 4) == 2
assert Solution().longestSubarray([10,1,2,4,7,2], 5) == 4
assert Solution().longestSubarray([4,2,2,2,4,4,2,2], 0) == 3

# Edge cases
assert Solution().longestSubarray([1], 0) == 1  # Single element
assert Solution().longestSubarray([1,1,1,1], 0) == 4  # All identical
assert Solution().longestSubarray([