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

Description

You are given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.

Example 1:

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

Output: 2

Explanation:
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4.
Therefore, the size of the longest subarray is 2.

Example 2:

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

Output: 4

Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Constraints:

1 <= nums.length <= 100,000
1 <= nums[i] <= 1,000,000,000
0 <= limit <= 1,000,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

A subarray is valid if the difference between its maximum and minimum is at most limit.
Brute force tries every possible starting index i, then extends the subarray to the right (j) while tracking the current min and max.
The moment max - min becomes greater than limit, extending further will only keep it invalid (or worse), so we break and move to the next i.

Algorithm

Initialize res = 1.
For each starting index i:
- Set mini = maxi = nums[i].
- For each j from i+1 to n-1:
  - Update mini = min(mini, nums[j])
  - Update maxi = max(maxi, nums[j])
  - If maxi - mini > limit, break.
  - Otherwise update res = max(res, j - i + 1).
Return res.

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        res = 1

        for i in range(n):
            mini = maxi = nums[i]
            for j in range(i + 1, n):
                mini = min(mini, nums[j])
                maxi = max(maxi, nums[j])
                if maxi - mini > limit:
                    break
                res = max(res, j - i + 1)

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Heap

Intuition

We want to find the longest continuous subarray where the difference between the maximum and minimum elements is less than or equal to the given limit.

A simple way would be to check all subarrays, but that would be too slow. Instead, we can use a sliding window approach where we expand the window to the right and shrink it from the left only when the condition becomes invalid.

The key challenge is to quickly know the maximum and minimum values in the current window. To handle this efficiently, we use:

a max heap to track the maximum value
a min heap to track the minimum value

Each heap also stores indices so we can remove elements that move out of the window.

Algorithm

Initialize two heaps:
- a max heap to store values (as negative for max behavior) along with their indices
- a min heap to store values along with their indices
Use two pointers:
- i for expanding the window to the right
- j for shrinking the window from the left
For each element at index i:
- Add it to both the max heap and the min heap
While the difference between the current maximum and minimum exceeds the limit:
- Move the left pointer j forward
- Remove elements from both heaps whose indices are less than j (they are outside the window)
After the window becomes valid again:
- Update the result with the current window length i - j + 1
Continue this process until all elements are processed
Return the maximum window length found.

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        maxHeap = []
        minHeap = []
        j = 0
        res = 0

        for i, v in enumerate(nums):
            heapq.heappush(maxHeap, (-v, i))
            heapq.heappush(minHeap, (v, i))

            while -maxHeap[0][0] - minHeap[0][0] > limit:
                j += 1
                while maxHeap and maxHeap[0][1] < j:
                    heapq.heappop(maxHeap)
                while minHeap and minHeap[0][1] < j:
                    heapq.heappop(minHeap)

            res = max(res, i - j + 1)

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Sorted Dict

Intuition

We want the longest continuous subarray where the difference between the maximum and minimum elements is less than or equal to the given limit.

Using a sliding window helps us avoid checking all subarrays. As we expand the window to the right, we need a way to always know the current minimum and maximum values inside the window.

To do this efficiently, we use a sorted data structure that keeps all elements of the current window in order. This allows us to:

get the minimum element from the beginning
get the maximum element from the end

If the difference between these two values becomes greater than the limit, we shrink the window from the left until it becomes valid again.

Algorithm

Initialize a sorted dictionary to store elements of the current window along with their frequencies.
Use two pointers:
- l as the left boundary of the window
- r as the right boundary of the window
For each element at index r:
- Insert it into the sorted dictionary and increase its count
While the difference between the largest and smallest keys in the sorted dictionary exceeds the limit:
- Remove the element at index l from the dictionary
- Decrease its count and delete it if the count becomes zero
- Move the left pointer l forward
Once the window is valid:
- Update the result with the current window size r - l + 1
Continue until all elements are processed
Return the maximum window length found.

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        tree = SortedDict()
        l = res = 0
        for r, x in enumerate(nums):
            tree[x] = tree.get(x, 0) + 1
            while tree.peekitem(-1)[0] - tree.peekitem(0)[0] > limit:
                y = nums[l]
                tree[y] -= 1
                if tree[y] == 0:
                    del tree[y]
                l += 1
            res = max(res, r - l + 1)
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Deque - I

Intuition

We want to find the longest continuous subarray where the difference between the maximum and minimum elements does not exceed the given limit.

A sliding window is a natural choice here, but the main challenge is efficiently tracking the current minimum and maximum in the window as it moves.

To solve this, we use two monotonic deques:

a monotonically increasing deque to keep track of the minimum values
a monotonically decreasing deque to keep track of the maximum values

These deques are maintained in such a way that their front elements always represent the minimum and maximum of the current window.

Algorithm

Initialize two deques:
- min_q to store elements in increasing order (front is the minimum)
- max_q to store elements in decreasing order (front is the maximum)
Use two pointers:
- l for the left boundary of the window
- r for expanding the window to the right
For each index r:
- Remove elements from the back of min_q while the current value is smaller
- Remove elements from the back of max_q while the current value is larger
- Add the current value to both deques
While the difference between the front of max_q and min_q exceeds the limit:
- If the element leaving the window equals the front of max_q, remove it
- If the element leaving the window equals the front of min_q, remove it
- Move the left pointer l forward
After the window becomes valid:
- Update the result using the current window size r - l + 1
Continue until all elements are processed
Return the maximum window length found

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        min_q = deque()  # mono increasing
        max_q = deque()  # mono decreasing
        l = res = 0

        for r in range(len(nums)):
            while min_q and nums[r] < min_q[-1]:
                min_q.pop()
            while max_q and nums[r] > max_q[-1]:
                max_q.pop()

            min_q.append(nums[r])
            max_q.append(nums[r])

            while max_q[0] - min_q[0] > limit:
                if nums[l] == max_q[0]:
                    max_q.popleft()
                if nums[l] == min_q[0]:
                    min_q.popleft()
                l += 1
            res = max(res, r - l + 1)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Deque - II

Intuition

We want the longest continuous subarray where the difference between the maximum and minimum values is at most limit.

A sliding window works well because the subarray must be continuous. As we expand the window to the right, we need to always know the current minimum and maximum in the window.

To track them efficiently, we maintain two monotonic deques:

inc (increasing deque): keeps possible minimum values in increasing order, so the front is the current minimum
dec (decreasing deque): keeps possible maximum values in decreasing order, so the front is the current maximum

Whenever the window becomes invalid (max - min > limit), we shrink it from the left by moving j forward and removing the left element from the deques if it matches their front.

Algorithm

Initialize two deques using the first element:
- inc for minimum tracking (monotonic increasing)
- dec for maximum tracking (monotonic decreasing)
Use two pointers:
- i expands the window to the right
- j shrinks the window from the left when needed
For each new element nums[i]:
- Maintain inc by popping from the back while the back is greater than nums[i]
- Maintain dec by popping from the back while the back is less than nums[i]
- Append nums[i] to both deques
If the window becomes invalid (dec[0] - inc[0] > limit):
- If the element leaving the window (nums[j]) equals the front of dec, pop it from dec
- If it equals the front of inc, pop it from inc
- Move j forward by 1 to shrink the window
After processing all elements, the valid window starts at j and ends at the last index, so its length is len(nums) - j
Return that length

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        inc = deque([nums[0]])
        dec = deque([nums[0]])
        res = 1
        j = 0

        for i in range(1, len(nums)):
            while inc and inc[-1] > nums[i]:
                inc.pop()
            while dec and dec[-1] < nums[i]:
                dec.pop()

            inc.append(nums[i])
            dec.append(nums[i])
            if dec[0] - inc[0] > limit:
                if dec[0] == nums[j]:
                    dec.popleft()
                if inc[0] == nums[j]:
                    inc.popleft()
                j += 1

        return len(nums) - j

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Using Regular Queues Instead of Monotonic Deques

A common mistake is to use regular queues or simply track a single max and min value. When the window shrinks, you lose track of the next maximum or minimum. Monotonic deques maintain candidates in order so that the front always gives the current extreme value for the window.

Removing the Wrong Element When Shrinking the Window

When the left pointer moves, you must only remove elements from the deques if they match the element leaving the window. A subtle bug occurs when you pop from the deque unconditionally, which can remove elements that are still inside the valid window.

Not Maintaining Deque Invariants Correctly

For the min deque to work correctly, it must remain monotonically increasing from front to back. For the max deque, it must remain monotonically decreasing. Forgetting to pop elements that violate these invariants before adding a new element leads to incorrect min/max values.

Comparing Indices Instead of Values

When using deques that store indices instead of values, a common mistake is to compare indices when you should compare values, or vice versa. Be consistent about what the deque stores and ensure comparisons use the appropriate array lookups.

Off-by-One Errors in Window Size Calculation

The window size is right - left + 1, not right - left. Forgetting the +1 when updating the result will undercount the longest valid subarray by one element.