/**
* 1438. 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.
*/
See the solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/LongestContinuousDiffLess.java
This solution is very clever and unique in its style. Hence, including it here so as to get exposure to this strategy.
Few observations:
- We can keep the data in increasing and decreasing queues and quickly lookup the min and max value in the queues to validate whether they cross the limit or otherwise.
- We can use a sliding window approach where we keep the left and right pointers and determine the size of the sub array as distance between left and right pointers.
- When limit is violated, we can move the left pointer to the right while dropping indexes that violate the limit condition.
With the above observations the algorithm is not that complicated anymore. The problem can be solved with the below code. With detailed inline comments the code is self-descriptive.
Here is the code:
public int longestSubarray(int[] nums, int limit) {
ArrayDeque<Integer> increasing = new ArrayDeque<> ();
ArrayDeque<Integer> decreasing = new ArrayDeque<> ();
//add the value in first index to the array
increasing.offer(nums[0]); decreasing.offer(nums[0]);
int len = nums.length;
int res = 1;
int i = 0;
//start loop from second index
for (int j = 1; j < len; j++) {
//if the increasing array constraints are not processed then drop the last value from the increasing array
while (!increasing.isEmpty() && increasing.getLast() > nums[j]) {
increasing.pollLast();
}
//if the decreasing array constraints are not processed then drop the last value from the decreasing array
while (!decreasing.isEmpty() && decreasing.getLast() < nums[j]) {
decreasing.pollLast();
}
//add the new element into the increasing / decreasing queues
increasing.offer(nums[j]);
decreasing.offer(nums[j]);
//if the difference between highest and lowest element in the two queues is
//greater than the limit then start dropping the elements from the largest/smallest elements from
//the queues as you iterate left index right (i is the left index)
while ((decreasing.peekFirst() - increasing.peekFirst()) > limit) {
if (increasing.peekFirst() == nums[i]) {
increasing.pollFirst();
}
if (decreasing.peekFirst() == nums[i]) {
decreasing.pollFirst();
}
//we keep moving the left pointer right and dropping items that violate the limit condition
//until the condition is no longer violated
i++;
}
//size of longest contiguous array is difference between right and left indices
//given we are validating the subarray is within the bounds above the left and right indexes must be
//pointing to valid indexes
res = Math.max(res, j-i+1);
}
return res;
}