MediumArrayQueueSliding WindowHeap (Priority Queue)Ordered SetMonotonic Queue

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1 approach, code in every language

You are given an integer array nums and an integer limit. Consider any contiguous subarray and look at the difference between its largest and smallest elements.

Return the length of the longest contiguous subarray for which that difference between the maximum and minimum values is at most limit.

Because the maximum and minimum of a window can both change as the window slides, the challenge is to track them efficiently while expanding and contracting.

Example 1

Input: nums = [8,2,4,7], limit = 4

Output: 2

The subarray [2,4] has a max-min difference of 2, which is within the limit, but extending to [2,4,7] gives a difference of 5, so no valid window is longer than 2.

Example 2

Input: nums = [10,1,2,4,7,2], limit = 5

Output: 4

The subarray [2,4,7,2] has maximum 7 and minimum 2, a difference of exactly 5, which satisfies the limit and spans four elements.

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9

Two Monotonic Deques

Keep a decreasing deque for the window maximum and an increasing deque for the window minimum, shrinking the window whenever their difference exceeds the limit.

Loading animation…

Intuition

To decide if a window is valid we only need its current maximum and minimum, so we maintain two monotonic deques of indices. The max deque stays decreasing, so its front is always the largest value in the window; the min deque stays increasing, so its front is always the smallest. As the right pointer expands, we pop from the back of each deque any indices whose values can no longer be the max or min, then append the new index. Whenever the front difference exceeds the limit, the window is invalid, so we move the left pointer forward and discard any deque front that has slid out of the window. The widest window that stays valid is the answer.

Algorithm walkthrough

1Create an empty max deque (kept decreasing by value) and an empty min deque (kept increasing by value), both storing indices; set left and best to 0.
2For each right index, pop indices from the back of the max deque while their value is less than or equal to nums[right], then push right; do the mirror operation on the min deque, popping while their value is greater than or equal to nums[right].
3The fronts of the two deques now give the maximum and minimum of the current window.
4While nums[maxDeque.front] - nums[minDeque.front] exceeds limit, advance left, and if a deque's front index is now before left, pop it from the front.
5Once the window is valid again, update best with right - left + 1.
6After processing every index, return best.

Implementation

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        from collections import deque
        max_dq = deque()  # decreasing values
        min_dq = deque()  # increasing values
        left = 0
        best = 0
        for right in range(len(nums)):
            while max_dq and nums[max_dq[-1]] <= nums[right]:
                max_dq.pop()
            max_dq.append(right)
            while min_dq and nums[min_dq[-1]] >= nums[right]:
                min_dq.pop()
            min_dq.append(right)
            while nums[max_dq[0]] - nums[min_dq[0]] > limit:
                left += 1
                if max_dq[0] < left:
                    max_dq.popleft()
                if min_dq[0] < left:
                    min_dq.popleft()
            best = max(best, right - left + 1)
        return best

Time

O(n)

Space

O(n)

Each index is pushed and popped from each deque at most once; the deques hold at most n indices in the worst case.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Steady Pressure Span is our own problem on the technique behind Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free