Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Asked at Uber
Problem
Given an array 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. The subarray must be contiguous.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | MEDIUM | View all Uber questions → |
How to Think About It
Brute force: check every subarray, compute max and min, verify diff <= limit — O(n^2).
Sliding window with two heaps (max-heap and min-heap) to track current window extrema.
Sliding window with two monotonic deques (one for max, one for min) — each element enqueued/dequeued at most once.
Ordered set approach (if language supports it) — insert elements and query first and last in O(log n).
Optimal: monotonic deque sliding window in O(n) time and O(n) space.
Optimal Approach
Use a sliding window with two monotonic deques: one decreasing (tracks max) and one increasing (tracks min). For each right pointer expansion, maintain the deques by removing out-of-window elements from the front and restoring monotonicity from the back. If the difference between the front of max-deque and front of min-deque exceeds limit, shrink the left pointer. Track the maximum window size. Each element is enqueued and dequeued at most once giving O(n) time.
What Trips People Up in Real Interviews
Clarify whether empty subarray is allowed (it is not — return 0 if no valid subarray).
Discuss why naive sliding window (one pointer per end) fails — we need to track both max and min.
Explain the monotonic deque invariant: front is always the candidate for max/min.
Edge case: all elements identical — entire array is valid.
Heaps approach is O(n log n) — mention trade-offs vs. monotonic deque O(n).
Solution Code
def longestSubarray(nums, limit):
from collections import deque
max_d = deque()
min_d = deque()
left = 0
result = 0
for right in range(len(nums)):
while max_d and nums[right] > nums[max_d[-1]]:
max_d.pop()
max_d.append(right)
while min_d and nums[right] < nums[min_d[-1]]:
min_d.pop()
min_d.append(right)
while nums[max_d[0]] - nums[min_d[0]] > limit:
left += 1
if max_d[0] < left:
max_d.popleft()
if min_d[0] < left:
min_d.popleft()
result = max(result, right - left + 1)
return resultFrequently Asked Questions
What is the Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit problem?
Given an array 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. The subarray must be contiguous.
How do you solve Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit is asked at Uber. It is a medium difficulty problem.
What are common mistakes on Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?
- Clarify whether empty subarray is allowed (it is not — return 0 if no valid subarray).
- Discuss why naive sliding window (one pointer per end) fails — we need to track both max and min.
- Explain the monotonic deque invariant: front is always the candidate for max/min.
- Edge case: all elements identical — entire array is valid.
- Heaps approach is O(n log n) — mention trade-offs vs. monotonic deque O(n).