Watch 10 video solutions for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit, a medium level problem involving Array, Queue, Sliding Window. This walkthrough by Fraz has 31,560 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= nums[i] <= 1090 <= limit <= 109Problem Overview: Given an integer array nums and a limit, find the length of the longest contiguous subarray where the absolute difference between the maximum and minimum elements is less than or equal to the limit.
Approach 1: Sliding Window with Monotonic Deques (O(n) time, O(n) space)
This approach maintains a dynamic window using two pointers. The key challenge is tracking the current window's minimum and maximum efficiently. Two monotonic deques solve this: one decreasing deque stores potential maximum values and one increasing deque stores potential minimum values. As you expand the right pointer, insert the new element while maintaining monotonic order. If max - min exceeds the limit, move the left pointer and remove elements leaving the window from the front of the deques.
Each element enters and leaves the deques at most once, so the total work is linear. This pattern appears frequently in sliding window problems that require maintaining window extrema efficiently. The deques act as a monotonic queue, allowing constant-time access to the current max and min.
Approach 2: Sliding Window with TreeMap (O(n log n) time, O(n) space)
This version uses a balanced ordered map such as Java's TreeMap. The sliding window expands by inserting each number into the map and tracking its frequency. The smallest and largest keys represent the current window's minimum and maximum. If the difference exceeds the limit, move the left pointer and decrement the frequency of the outgoing value, removing it when the count reaches zero.
Each insertion and deletion costs O(log n) due to tree balancing. The advantage is conceptual simplicity since the ordered map automatically keeps elements sorted. This approach is useful when a language provides efficient ordered set or map implementations but monotonic deque patterns feel less familiar.
Recommended for interviews: The monotonic deque sliding window is the expected optimal solution with O(n) time. It demonstrates mastery of window invariants and specialized queue structures. The TreeMap approach still shows solid understanding but is usually considered a step below the optimal linear solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Monotonic Deques | O(n) | O(n) | Best overall solution when you need constant-time min and max tracking inside a sliding window |
| Sliding Window with TreeMap | O(n log n) | O(n) | Simpler to implement when the language provides ordered maps or sets |