Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Problem
Given an integer array nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.
- 1 ≤ nums.length ≤ 10⁵
- 1 ≤ nums[i] ≤ 10⁹
- 0 ≤ limit ≤ 10⁹
Example
nums = [8,2,4,7], limit = 42Starting with the full array, the absolute difference between max and min is 8 - 2 = 6, which exceeds the limit 4. The algorithm uses two deques to track the max and min values in the current window. It expands the right pointer, updating these deques to maintain monotonicity. When the difference between the front elements of the max and min deques exceeds the limit, it moves the left pointer forward, popping elements from the deques if they are leaving the window. The longest valid window found is [2,4] or [4,7], both length 2.
Approach
Straightforward Solution
A brute-force approach would check every subarray, calculating max and min each time, resulting in O(n^2) time complexity, which is infeasible for large inputs.
Core Observation
The absolute difference between any two elements in a subarray is determined by the difference between the maximum and minimum elements in that subarray. Maintaining these extremes efficiently is key to validating the window.
Path to Optimal
The key recognition signals are 'longest continuous subarray', 'absolute difference between any two elements', and 'limit'. These indicate a Sliding Window pattern combined with data structures that can track max and min efficiently. Using two monotonic deques to maintain the max and min values in O(1) time per operation allows the window to expand and contract while checking the validity condition in O(n) time overall.
Optimal Approach
Use a sliding window with two monotonic deques: one to track the maximum values in descending order, and one to track the minimum values in ascending order. Expand the right pointer, updating the deques. If the difference between the front elements of the max and min deques exceeds the limit, move the left pointer forward, removing elements from the deques if they exit the window. Track the maximum window size during this process.
Time
O(n)
Each element is added and removed at most once from each deque, and the right and left pointers each traverse the array once, resulting in linear time complexity.
Space
O(n)
The two deques can each hold up to n elements in the worst case, so the auxiliary space is O(n). This space is necessary to maintain the monotonic properties for efficient max and min tracking.
Pattern Spotlight
Sliding Window (Monotonic Queue Optimization)
When a problem requires maintaining the maximum and minimum within a sliding window efficiently, use two monotonic deques to track these extremes, enabling O(1) updates and O(n) total time by contracting the window whenever the constraint is violated.
Solution
| 1 | class Solution: |
| 2 | def longestSubarray(self, nums: list[int], limit: int) -> int: |
| 3 | maxd = deque() |
| 4 | mind = deque() |
| 5 | left = 0 |
| 6 | best = 0 |
| 7 | |
| 8 | for right in range(len(nums)): |
| 9 | while maxd and nums[right] > maxd[-1]: |
| 10 | maxd.pop() |
| 11 | maxd.append(nums[right]) |
| 12 | |
| 13 | while mind and nums[right] < mind[-1]: |
| 14 | mind.pop() |
| 15 | mind.append(nums[right]) |
| 16 | |
| 17 | while maxd[0] - mind[0] > limit: |
| 18 | if nums[left] == maxd[0]: |
| 19 | maxd.popleft() |
| 20 | if nums[left] == mind[0]: |
| 21 | mind.popleft() |
| 22 | left += 1 |
| 23 | |
| 24 | best = max(best, right - left + 1) |
| 25 | |
| 26 | return best |
Step-by-Step Solution
Maintain Monotonic Deques to Track Max and Min Values While Expanding Window
| 8 | for right in range(len(nums)): |
| 9 | while maxd and nums[right] > maxd[-1]: |
| 10 | maxd.pop() |
| 11 | maxd.append(nums[right]) |
| 13 | while mind and nums[right] < mind[-1]: |
| 14 | mind.pop() |
| 15 | mind.append(nums[right]) |
Objective
To update the max and min deques to reflect the current window's extremes as the right pointer moves forward.
Key Insight
Monotonic deques maintain elements in sorted order by popping smaller (for max deque) or larger (for min deque) elements from the back before appending the new element. This ensures the front always holds the current maximum or minimum. By doing this at each step, the algorithm can access the window's max and min in O(1) time, enabling efficient validity checks.
Interview Quick-Check
Core Logic
Monotonic deques maintain the max and min values in O(1) time per update by popping elements that violate the monotonic property before appending the new element.
State & Boundaries
The right pointer expands the window by one element each iteration, updating the deques to include the new element while preserving monotonicity.
Common Pitfalls & Bugs
Failing to pop elements from the back of the deques before appending the new element breaks the monotonic property, leading to incorrect max/min tracking.
Shrink Window from Left to Restore Validity When Limit is Exceeded
| 17 | while maxd[0] - mind[0] > limit: |
| 18 | if nums[left] == maxd[0]: |
| 19 | maxd.popleft() |
| 20 | if nums[left] == mind[0]: |
| 21 | mind.popleft() |
| 22 | left += 1 |
Objective
To move the left pointer forward and remove elements from the deques when the current window violates the limit constraint.
Key Insight
When the difference between the maximum and minimum values exceeds the limit, the window is invalid. By moving the left pointer forward and removing the outgoing element from the fronts of the deques if it matches, the algorithm restores validity. This contraction ensures the window always satisfies the problem's constraint while maximizing its size.
Interview Quick-Check
Core Logic
The window shrinks from the left by incrementing the left pointer and removing elements from the front of the deques if they are leaving the window, maintaining accurate max and min tracking.
State & Boundaries
The while loop continues shrinking the window until the difference between max and min is within the limit.
Common Pitfalls & Bugs
Not removing the outgoing element from the deques when it equals the front leads to stale max/min values and incorrect window validity checks.
Track and Update the Maximum Valid Window Size
| 24 | best = max(best, right - left + 1) |
Objective
To record the size of the largest valid window found during the iteration.
Key Insight
After ensuring the window is valid, the algorithm calculates its size and updates the best result if this window is larger. This step accumulates the final answer by continuously tracking the maximum window length that satisfies the limit constraint.
Interview Quick-Check
Core Logic
Update the best window size by comparing the current window length (right - left + 1) with the previously recorded maximum.
Complexity
This update is O(1) per iteration, preserving the overall linear time complexity.
Return the Length of the Longest Valid Subarray
| 26 | return best |
Objective
To return the final computed maximum window size after processing the entire array.
Key Insight
The variable tracking the best window size holds the length of the longest subarray meeting the limit condition. Returning this value completes the solution.
Interview Quick-Check
Core Logic
Return the maximum window size found, which represents the longest continuous subarray with absolute difference within the limit.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
while maxd[0] - mind[0] > limit:Check if the current window violates the limit constraint.
Comparing the front elements of the max and min deques gives the current window's max-min difference, which must be within the limit.
while maxd and nums[right] > maxd[-1]:Pop elements from the max deque's back while the current element is greater.
Removing smaller elements from the back preserves the descending order, ensuring the front is always the maximum in the window.
while mind and nums[right] < mind[-1]:Pop elements from the min deque's back while the current element is smaller.
Removing larger elements from the back preserves the ascending order, ensuring the front is always the minimum in the window.
maxd = deque()Initialize a deque to track maximum values in the current window.
This deque maintains elements in descending order, allowing O(1) access to the current window's maximum value at its front.
mind = deque()Initialize a deque to track minimum values in the current window.
This deque maintains elements in ascending order, allowing O(1) access to the current window's minimum value at its front.
if nums[left] == maxd[0]:If the left element equals the max deque's front, remove it as it leaves the window.
Removing the outgoing element from the max deque keeps the max value accurate for the new window after shrinking.
if nums[left] == mind[0]:If the left element equals the min deque's front, remove it as it leaves the window.
Removing the outgoing element from the min deque keeps the min value accurate for the new window after shrinking.
left += 1Increment the left pointer to shrink the window.
Moving the left pointer forward restores the window's validity by excluding elements causing the violation.
best = max(best, right - left + 1)Update the best window size with the current valid window length.
Tracking the maximum window length ensures the final answer reflects the longest valid subarray found.
maxd.pop()Remove the smaller elements from the max deque's back.
This step enforces the monotonic decreasing property of the max deque, critical for efficient max retrieval.
maxd.append(nums[right])Append the current element to the max deque.
Adding the new element maintains the deque's role as a max tracker for the current window.
mind.pop()Remove the larger elements from the min deque's back.
This step enforces the monotonic increasing property of the min deque, critical for efficient min retrieval.
mind.append(nums[right])Append the current element to the min deque.
Adding the new element maintains the deque's role as a min tracker for the current window.
maxd.popleft()Remove the front element from the max deque if it matches the outgoing element.
This ensures the max deque reflects only elements inside the current window boundaries.
mind.popleft()Remove the front element from the min deque if it matches the outgoing element.
This ensures the min deque reflects only elements inside the current window boundaries.
left = 0Initialize the left pointer of the sliding window.
The left pointer marks the start of the current window and moves forward to shrink the window when constraints are violated.
for right in range(len(nums)):Iterate over the array with the right pointer expanding the window.
The right pointer moves forward one element at a time, expanding the window and triggering updates to the max and min deques.
best = 0Initialize the variable to track the best (maximum) window size found.
This variable accumulates the length of the longest valid subarray encountered during iteration.
return bestReturn the length of the longest valid subarray found.
This final return provides the solution to the problem as required.
Test Your Understanding
Why do we need two monotonic deques instead of just one to maintain the window validity?
Because the validity condition depends on the difference between the maximum and minimum elements in the window, we must track both extremes efficiently. One deque tracks the maximum values in descending order, and the other tracks the minimum values in ascending order, allowing constant-time access to both ends and enabling quick window adjustments.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit drill