Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Problem Description
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
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The simplest way to solve this problem is by checking every possible subarray and verifying if it meets the condition, i.e., its maximum and minimum difference is less than or equal to the given limit. This involves calculating the max and min for all subarrays which can be computationally expensive but forms the foundation of understanding the problem.
Steps:
- Iterate over each starting index of a subarray.
- For each starting index, iterate over each possible ending index, maintaining the current maximum and minimum in the subarray.
- If at any point the difference between the maximum and minimum exceeds the limit, move to the next starting index.
- Keep track of the length of the longest valid subarray found.
Code:
- Time Complexity: O(N^2) - All possible subarrays are considered, each requiring potentially a scan from start to end.
- Space Complexity: O(1) - Only a few integer variables utilized for computation.
2. Optimized Sliding Window with Two Deques
Intuition:
The brute force solution is inefficient due to redundant checks for the max and min. A more optimal solution can maintain a sliding window of elements, while keeping the current maximum and minimum within this window through deques. As the sliding window expands, the deques are used to update and maintain the max and min efficiently.
Steps:
- Use two deques to store the indices of the elements. One deque stores indices in decreasing order to get the minimum, and another in increasing order for the maximum.
- Initialize your window's start pointer
leftto zero. - Expand the window by moving the
rightpointer and update deques. - Check the condition by comparing the max and min using the front of both deques.
- If the condition is not met (max - min > limit), increment the
leftpointer. - Calculate the maximum length of the window that satisfies the condition.
- Return the result.
Code:
- Time Complexity: O(N) - Each element is added and removed from the deque at most once.
- Space Complexity: O(N) - Space for the two deques holding indices.