NeetCode #258LC-1438MediumSliding Window
← Back to All Problems#258 · #1438 · Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit(绝对差不超过限制的最长连续子数组)
📌 Problem Statement & Constraints
Given an array of integers
nums and an integer limit, return the size of the longest subarray such that the absolute difference between any two of its elements is at most limit. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9, 0 <= limit <= 10^9.💡 Core Algorithmic Approaches
- A window satisfies the condition exactly when
max(window) - min(window) <= limit. - So we need a sliding window with efficient access to its maximum and minimum -- two monotonic deques.
- One deque keeps indices in decreasing value order (front = maximum); the other keeps increasing order (front = minimum).
- When the difference exceeds
limit, advance the left pointer and evict it from either deque if it is at the front.
💻 Benchmark Python3 Implementation
class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
from collections import deque
maxq = deque() # decreasing values, front is the max
minq = deque() # increasing values, front is the min
l = 0
best = 0
for r, x in enumerate(nums):
while maxq and nums[maxq[-1]] <= x:
maxq.pop()
maxq.append(r)
while minq and nums[minq[-1]] >= x:
minq.pop()
minq.append(r)
while nums[maxq[0]] - nums[minq[0]] > limit:
if maxq[0] == l:
maxq.popleft()
if minq[0] == l:
minq.popleft()
l += 1
best = max(best, r - l + 1)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index is pushed and popped at most once from each deque.
💾 Space Complexity
O(n) for the two deques in the worst case.
⚠️ Interview Pitfalls & Follow-ups
- Using
max(window)andmin(window)on the fly: O(n) per step, giving O(n^2). - Evicting from only one deque when shrinking: the leaving index may be at the front of either deque, so both must be checked.
- Storing values instead of indices: you cannot tell whether the front has left the window.
- Using
<in the back-popping comparisons: either<or<=works, but be consistent;<=keeps the deques strictly monotone and slightly smaller.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner