MediumArrayQueueSliding WindowHeapOrdered SetMonotonic QueueUpdated Sep 2026

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

Asked at Uber

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You get an array of integers nums and an integer limit. Find the longest contiguous subarray (a run of neighbouring elements) whose elements are all close to each other: the absolute difference between the largest and the smallest value inside that run must be at most limit.

Return the length of that longest run. The subarray must be non-empty, so the answer is at least 1.

Note that the rule only cares about the biggest and smallest element in the window. If max - min <= limit, then every pair inside the window is fine too, because the largest gap is always between the max and the min.

Only max and min matter

numsmax-min = 282470123[2,4] is valid: 4 - 2 = 2 <= 4numsmax-min = 582470123[2,4,7] is invalid: 7 - 2 = 5 > 4
A window is valid when its largest value minus its smallest value is at most limit.

Constraints

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

Examples

Example 1
Inputnums = [8,2,4,7], limit = 4
Output2
WhyThe window [8,2] fails because 8 - 2 = 6 > 4. The window [2,4,7] fails because 7 - 2 = 5 > 4. Windows like [2,4] or [4,7] have max - min = 2 and 3, both within 4, so the best length is 2.
Example 2
Inputnums = [10,1,2,4,7,2], limit = 5
Output4
WhyThe run [2,4,7,2] has max 7 and min 2, and 7 - 2 = 5, which is allowed. No longer run works, so the answer is 4.
Example 3
Inputnums = [4,2,2,2,4,4,2,2], limit = 0
Output3
WhyWith limit 0 all values in the window must be equal. The longest block of the same value is [2,2,2] or [4,4], so the answer is 3.

Asked At

1 companies
CompanyDifficulty
UberMediumView all Uber questions →

How to Think About It

1

Brute force: check every subarray, compute max and min, verify diff <= limit — O(n^2).

2

Sliding window with two heaps (max-heap and min-heap) to track current window extrema.

3

Sliding window with two monotonic deques (one for max, one for min) — each element enqueued/dequeued at most once.

4

Ordered set approach (if language supports it) — insert elements and query first and last in O(log n).

5

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.

Sliding window with two monotonic deques

numswindow82470123leftrightright reaches index 1: max 8, min 2, gap 6 > 4, somove leftnumswindow82470123leftrightafter dropping 8 the window [2,4] is valid, best = 2numswindow82470123leftrightright reaches 7: max 7, min 2, gap 5 > 4, so shrinkagainmax_d front = window maxmin_d front = window minshrink while max - min > limitbest = max(best, right - left + 1)
One deque keeps the window maximum at its front, the other keeps the minimum; shrink from the left while they disagree by more than limit.
ComplexityTime O(n)Space O(n)Each index enters and leaves each deque at most once, so the whole scan is linear; the two deques can hold up to n indices.

What Trips People Up in Real Interviews

1

Clarify whether empty subarray is allowed (it is not — return 0 if no valid subarray).

2

Discuss why naive sliding window (one pointer per end) fails — we need to track both max and min.

3

Explain the monotonic deque invariant: front is always the candidate for max/min.

4

Edge case: all elements identical — entire array is valid.

5

Heaps approach is O(n log n) — mention trade-offs vs. monotonic deque O(n).

Solution Code

O(n) time
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 result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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).