# Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit)
Canonical: https://scaleengineer.com/dsa/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Heap (Priority Queue), Ordered Set, Queue, Monotonic Queue
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix), [Visa](https://scaleengineer.com/companies/visa), [eBay](https://scaleengineer.com/companies/ebay), [Capital One](https://scaleengineer.com/companies/capital-one), [PhonePe](https://scaleengineer.com/companies/phonepe), [Databricks](https://scaleengineer.com/companies/databricks), [Moloco](https://scaleengineer.com/companies/moloco)
---
## Problem
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

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`
* `0 <= limit <= 109`

# Approaches
## Brute Force with Optimization
This approach iterates through all possible continuous subarrays. For each starting point `i`, it expands a window to the right with an endpoint `j`. While expanding, it keeps track of the minimum and maximum values within the current subarray `nums[i...j]`.
**Time:** O(n^2), where n is the length of `nums`. The two nested loops dominate the runtime. · **Space:** O(1), as we only use a few variables to store the state.
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large inputs, leading to a "Time Limit Exceeded" error on most platforms.
### Explanation
We use two nested loops. The outer loop fixes the starting index `i` of the subarray, and the inner loop iterates through all possible ending indices `j` starting from `i`.
For each subarray `nums[i...j]`, we maintain the minimum (`minVal`) and maximum (`maxVal`) elements seen so far within that specific subarray.
In the inner loop, as we consider `nums[j]`, we update `minVal` and `maxVal`.
We then check if the condition `maxVal - minVal <= limit` holds.
If it holds, the current subarray is valid, and we update our answer for the maximum length: `maxLength = max(maxLength, j - i + 1)`.
If the condition is violated (`maxVal - minVal > limit`), we can break the inner loop. This is a small optimization because any further extension of the subarray from the current starting point `i` will also violate the condition.

```java
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int maxLength = 0;
        for (int i = 0; i < nums.length; i++) {
            int minVal = nums[i];
            int maxVal = nums[i];
            for (int j = i; j < nums.length; j++) {
                minVal = Math.min(minVal, nums[j]);
                maxVal = Math.max(maxVal, nums[j]);
                if (maxVal - minVal <= limit) {
                    maxLength = Math.max(maxLength, j - i + 1);
                } else {
                    // Optimization: If the condition is violated,
                    // any further extension from 'i' will also be invalid.
                    break;
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
*   Initialize `maxLength = 0`.
*   Iterate through the array with an index `i` from `0` to `n-1` (this will be the start of the subarray).
*   Inside this loop, initialize `minVal = nums[i]` and `maxVal = nums[i]`.
*   Start a second loop with an index `j` from `i` to `n-1` (this will be the end of the subarray).
*   Update `minVal = min(minVal, nums[j])` and `maxVal = max(maxVal, nums[j])`.
*   If `maxVal - minVal <= limit`, update `maxLength = max(maxLength, j - i + 1)`.
*   If `maxVal - minVal > limit`, break the inner loop, as any further extension will also be invalid.
*   After the loops complete, return `maxLength`.

## Sliding Window with Self-Balancing BST (TreeMap)
This approach uses a sliding window, defined by a `left` and `right` pointer. To efficiently find the minimum and maximum elements within the window, we use a self-balancing binary search tree. In Java, a `TreeMap` is a suitable data structure for this, as it keeps its keys sorted.
**Time:** O(n log n). The `right` pointer moves `n` times. In each step, we might perform insertions and deletions on the `TreeMap`. These operations take O(log k) time, where `k` is the number of distinct elements in the window (`k <= n`). · **Space:** O(n) in the worst case, where the `TreeMap` might need to store all `n` elements if they are all distinct and part of a valid window.
**Pros:** Significantly more efficient than the brute-force approach.; Passes most test cases on competitive programming platforms.
**Cons:** The logarithmic factor from the `TreeMap` operations makes it slightly slower than the most optimal solution.
### Explanation
The core idea is to maintain a window of elements that satisfies the condition `max - min <= limit`. We expand this window by moving the `right` pointer and shrink it by moving the `left` pointer.
We use a `TreeMap` to store the elements in the current window and their frequencies. The keys of the `TreeMap` are the numbers, and the values are their counts.
We iterate through the array with the `right` pointer. For each element `nums[right]`, we add it to our `TreeMap`.
The minimum element in the window is `treeMap.firstKey()` and the maximum is `treeMap.lastKey()`.
We check if `treeMap.lastKey() - treeMap.firstKey() > limit`. If it is, our window is invalid. We must shrink it from the left.
To shrink the window, we remove `nums[left]` from the `TreeMap` (by decrementing its count, and removing the key if the count becomes zero) and increment the `left` pointer. We repeat this until the window becomes valid again.
After ensuring the window is valid, we calculate its size (`right - left + 1`) and update the `maxLength`.

```java
import java.util.TreeMap;

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int left = 0;
        int maxLength = 0;
        for (int right = 0; right < nums.length; right++) {
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            
            while (map.lastKey() - map.firstKey() > limit) {
                map.put(nums[left], map.get(nums[left]) - 1);
                if (map.get(nums[left]) == 0) {
                    map.remove(nums[left]);
                }
                left++;
            }
            
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}
```
### Algorithm
*   Initialize `left = 0`, `maxLength = 0`.
*   Initialize an empty `TreeMap` called `map` to store counts of numbers in the window.
*   Iterate `right` from `0` to `n-1`:
    *   Add `nums[right]` to the `map`, incrementing its count.
    *   While `map.lastKey() - map.firstKey() > limit`:
        *   Decrement the count of `nums[left]` in the `map`.
        *   If the count of `nums[left]` becomes `0`, remove it from the `map`.
        *   Increment `left`.
    *   Update `maxLength = max(maxLength, right - left + 1)`.
*   Return `maxLength`.

## Sliding Window with Two Deques
This is the most optimal approach. It uses a sliding window and two Deques (Double-Ended Queues) to keep track of the minimum and maximum values in the current window in O(1) time on average. One deque maintains potential maximums in decreasing order, and the other maintains potential minimums in increasing order.
**Time:** O(n). Each element is added to and removed from each deque at most once. The `left` and `right` pointers traverse the array once. This gives a linear time complexity. · **Space:** O(n). In the worst case (e.g., a sorted array), the deques could store indices for all elements. In the best case, it's O(1).
**Pros:** Most efficient solution with linear time complexity.
**Cons:** Can be slightly more complex to understand and implement correctly compared to the `TreeMap` approach.
### Explanation
We maintain a sliding window `[left, right]`. We also use two deques: `maxDeque` and `minDeque`. These deques will store the *indices* of the elements.
*   `maxDeque`: Stores indices of elements in the current window in decreasing order of their values. The front of the deque always holds the index of the maximum element in the window.
*   `minDeque`: Stores indices of elements in the current window in increasing order of their values. The front of the deque always holds the index of the minimum element in the window.
As we iterate with the `right` pointer, we add `nums[right]` to the window. To maintain the properties of the deques, before adding the index `right`, we remove from the back of `maxDeque` all indices `i` where `nums[i] <= nums[right]`, and do the opposite for `minDeque`. Then we add `right` to the back of both deques.
The maximum in the current window is `nums[maxDeque.peekFirst()]` and the minimum is `nums[minDeque.peekFirst()]`. We check if their difference exceeds the `limit`. If it does, we shrink the window from the left by incrementing `left` and removing `left` from the deques if it was the head.
After each step, the window `[left, right]` is valid, and we update `maxLength`.

```java
import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxDeque = new LinkedList<>();
        Deque<Integer> minDeque = new LinkedList<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < nums.length; right++) {
            // Maintain the maxDeque in decreasing order of values
            while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] <= nums[right]) {
                maxDeque.pollLast();
            }
            maxDeque.addLast(right);

            // Maintain the minDeque in increasing order of values
            while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= nums[right]) {
                minDeque.pollLast();
            }
            minDeque.addLast(right);

            // Check if the current window is invalid and shrink it until it's valid
            while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) {
                if (maxDeque.peekFirst() == left) {
                    maxDeque.pollFirst();
                }
                if (minDeque.peekFirst() == left) {
                    minDeque.pollFirst();
                }
                left++;
            }

            // The window [left, right] is now valid. Update the max length.
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}
```
### Algorithm
*   Initialize `left = 0`, `maxLength = 0`.
*   Initialize an empty `maxDeque` and an empty `minDeque` to store indices.
*   Iterate `right` from `0` to `n-1`:
    *   While `maxDeque` is not empty and the value at its last index is less than or equal to `nums[right]`, remove the last element from `maxDeque`.
    *   Add `right` to the end of `maxDeque`.
    *   While `minDeque` is not empty and the value at its last index is greater than or equal to `nums[right]`, remove the last element from `minDeque`.
    *   Add `right` to the end of `minDeque`.
    *   While the difference between the values at the front of the deques (`nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()]`) is greater than `limit`:
        *   If the index at the front of `maxDeque` is `left`, remove it.
        *   If the index at the front of `minDeque` is `left`, remove it.
        *   Increment `left` to shrink the window.
    *   Update `maxLength = max(maxLength, right - left + 1)`.
*   Return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int longestSubarray(int[] nums, int limit) {
    TreeMap<Integer, Integer> tm = new TreeMap<>();
    int ans = 0, j = 0;
    for (int i = 0; i < nums.length; ++i) {
      tm.put(nums[i], tm.getOrDefault(nums[i], 0) + 1);
      while (tm.lastKey() - tm.firstKey() > limit) {
        tm.put(nums[j], tm.get(nums[j]) - 1);
        if (tm.get(nums[j]) == 0) {
          tm.remove(nums[j]);
        }
        ++j;
      }
      ans = Math.max(ans, i - j + 1);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: int longestSubarray ( vector < int >& nums , int limit ) { multiset < int > s ; int ans = 0 , j = 0 ; for ( int i = 0 ; i < nums . size (); ++ i ) { s . insert ( nums [ i ]); while ( * s . rbegin () - * s . begin () > limit ) { s . erase ( s . find ( nums [ j ++ ])); } ans = max ( ans , i - j + 1 ); } return ans ; } };
```

### Python

```python
from sortedcontainers import SortedList class Solution : def longestSubarray ( self , nums : List [ int ], limit : int ) -> int : sl = SortedList () ans = j = 0 for i , v in enumerate ( nums ): sl . add ( v ) while sl [ - 1 ] - sl [ 0 ] > limit : sl . remove ( nums [ j ]) j += 1 ans = max ( ans , i - j + 1 ) return ans
```