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 <= 109This approach uses the sliding window technique along with two deques to efficiently keep track of the maximum and minimum values in the current window.
We maintain two deques - one for the indices of the maximum values and another for the minimum values, within the current window of the array, called `nums`. By utilizing the sliding window, we can dynamically adjust the start and end of the window based on whether the condition of the absolute difference being less than or equal to the limit is satisfied.
The python implementation uses two deques, `min_deque` and `max_deque`, to maintain the indices of the current window's minimum and maximum elements.
As we iterate with the `right` pointer across each element, we adjust the deques to hold only the valid elements within the current window range. If at any point the difference between the max and min exceeds the specified limit, the `left` pointer is incremented to reduce the window size.
C++
Java
JavaScript
C#
Time Complexity: O(n), where n is the length of the array, because each element is added and removed from the deque at most once.
Space Complexity: O(n), due to the size of the deques which in the worst case can hold all elements.
This approach uses a sliding window implemented with a TreeMap to automatically manage and get minimum and maximum values from the current window range.
By leveraging the automatic ordering of keys within a TreeMap, this approach ensures the retrieval and conditional check of both minimum and maximum values within a determined window is efficient.
Upon the boundary violation concerning the permissible limit, the left pointer incrementally adjusts, pruning the TreeMap until the condition is restored.
Time Complexity: O(n log n); each insertion and deletion operation on TreeMap takes log n time.
Space Complexity: O(n); due to the additional space required by the TreeMap.
| Approach | Complexity |
|---|---|
| Sliding Window with Deques | Time Complexity: O(n), where n is the length of the array, because each element is added and removed from the deque at most once. Space Complexity: O(n), due to the size of the deques which in the worst case can hold all elements. |
| Sliding Window with TreeMap (Java) | Time Complexity: O(n log n); each insertion and deletion operation on TreeMap takes log n time. Space Complexity: O(n); due to the additional space required by the TreeMap. |
Leetcode - Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit • Fraz • 30,327 views views
Watch 9 more video solutions →Practice Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor