---
tags: data_structure_python
---

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

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: All subarrays are: 
[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.

**Example 3:**

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

**Example 4:**

Input: nums = [1,5,6,7,8,10,6,5,6], limit = 4
Output: 5 
Explanation: 10 - 5 becomes 5. [6,7,8,10,6] is the correct window.

**Constraints:**

- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 0 <= limit <= 10^9

# Solution

### Solution 1: Sliding Window (Time Limit Exceeding).

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        m, beg, end = len(nums), 0, 0
        maxi = -float("inf")
        max_val = min_val = nums[0]   
    
        while end < m:
            
            max_value = max(nums[beg:end+1])
            min_value = min(nums[beg:end+1])
            
            while max_value - min_value > limit:
                beg += 1
                max_value = max(nums[beg:end+1])
                min_value = min(nums[beg:end+1])

            maxi = max(maxi, end-beg+1)
            end +=1
            
        return maxi

### Solution 2: Sliding window + monotonic queue.

**Monotonic queue** are used to keep track of running max/min inside sliding window. This bypass the time exceed limit of above solution.

Useful blog posts:

- [[Python] Two Monotonic Queues with Sliding Window, O(N)](https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/777047/Python-Two-Monotonic-Queues-with-Sliding-Window-O(N))
- [Monotonic Queue Summary I](https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/204290/Monotonic-Queue-Summary)
- [Monotonic Queue Summary II](https://medium.com/@gregsh9.5/monotonic-queue-notes-980a019d5793)

from collections import deque

class Solution:
    
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        # Amortized time complexity of Monotonic Queue: O(1)
        # Time complexity: O(n) * O(1) = O(n). 
        # Space complexity: O(2n) ~= O(n).
        
        m, beg, end = len(nums), 0, 1
        # Create Monotonic Queue to keep track of max/min value indices.
        max_mq, min_mq = deque([0]), deque([0])
        maxi = 1
        
        while end < m:
            
            # 1. Keep track of running maximum inside sliding window.
            while max_mq and nums[max_mq[-1]] < nums[end]:
                max_mq.pop()
            max_mq.append(end)
            
            # 2. Keep track of running minimum inside sliding window.
            while min_mq and nums[min_mq[-1]] > nums[end]:
                min_mq.pop()
            min_mq.append(end)
            
            # 3. Move `beg` ahead while difference between largest/smallest is greater than limit.
            while max_mq and min_mq and nums[max_mq[0]] - nums[min_mq[0]] > limit:
                beg += 1
                
                if max_mq[0] < beg:
                    max_mq.popleft()
                    
                if min_mq[0] < beg:
                    min_mq.popleft()
                
            maxi = max(maxi, end-beg+1)
            end +=1
            
        return maxi