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

Q: What is the time complexity of Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?

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.

Q: What pattern does Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit use?

The Pattern: Sliding Window (Monotonic Queue Optimization) The Heuristic: 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.

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

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

Output: 2

Starting 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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Solution

Python

1class Solution:
  def longestSubarray(self, nums: list[int], limit: int) -> int:
      maxd = deque()
      mind = deque()
      left = 0
      best = 0
7
      for right in range(len(nums)):
          while maxd and nums[right] > maxd[-1]:
              maxd.pop()
          maxd.append(nums[right])
12
          while mind and nums[right] < mind[-1]:
              mind.pop()
          mind.append(nums[right])
16
          while maxd[0] - mind[0] > limit:
              if nums[left] == maxd[0]:
                  maxd.popleft()
              if nums[left] == mind[0]:
                  mind.popleft()
              left += 1
23
          best = max(best, right - left + 1)
25
      return best

Step-by-Step Solution

1

Maintain Monotonic Deques to Track Max and Min Values While Expanding Window

8for right in range(len(nums)):
  while maxd and nums[right] > maxd[-1]:
      maxd.pop()
  maxd.append(nums[right])
  while mind and nums[right] < mind[-1]:
      mind.pop()
  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.

2

Shrink Window from Left to Restore Validity When Limit is Exceeded

To move the left pointer forward and remove elements from the deques when the current window violates the limit constraint.

3

Track and Update the Maximum Valid Window Size

To record the size of the largest valid window found during the iteration.

4

Return the Length of the Longest Valid Subarray

To return the final computed maximum window size after processing the entire array.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 17 Critical

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.

Line 9 Critical

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.

Line 13 Critical

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.

Full line-by-line criticality + rationale for all 19 lines available on Pro.

Test Your Understanding

Why do we need two monotonic deques instead of just one to maintain the window validity?

See the answer with Pro.

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

or drill a free problem

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`

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])`