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

Medium Arrays & Hashing Sliding Window · Variable Original on LeetCode

Reported atUberPhonePe

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit is a medium arrays & hashing problem solved with the sliding window · variable pattern. The best approach, optimal (sliding window + two monotonic deques), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

You are given an array of positive integers nums and an integer limit. Find the length of the longest contiguous subarray in which the absolute difference between any two elements is at most limit.

Since the largest difference inside a subarray is always its maximum minus its minimum, this is the same as asking for the longest subarray whose max - min <= limit. A single element always qualifies, so the answer is at least 1.

Examples

Example 1

Input
nums = [3, 9, 7, 8, 10, 2], limit = 3
Output
4
Why
[9, 7, 8, 10] has max 10 and min 7, a difference of 3. Any longer window would include 3 or 2 and break the limit.

Example 2

Input
nums = [6, 6, 6, 1, 6], limit = 0
Output
3
Why
With limit 0 every value in the window must be equal: the first three 6s.

Example 3

Input
nums = [2, 11, 4], limit = 10
Output
3
Why
The largest difference in the whole array is 11 - 2 = 9, which is within the limit.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute forceO(n²)O(1)
Optimal (sliding window + two monotonic deques)O(n)O(n)

1Brute force

TimeO(n²)For each of n starts the inner loop can run to the end of the array.
SpaceO(1)Only the running max, min and indices.

Fix each start index and extend the window to the right while tracking its running max and min. Stop as soon as max - min exceeds the limit, because extending further can only make it worse.

  1. For each start i, set hi = lo = nums[i].
  2. For j from i to n - 1: update hi and lo with nums[j]; if hi - lo > limit, break; else best = max(best, j - i + 1).
  3. Return best.
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int n = nums.length, best = 0;
        for (int i = 0; i < n; i++) {
            int hi = nums[i], lo = nums[i];
            for (int j = i; j < n; j++) {
                hi = Math.max(hi, nums[j]);
                lo = Math.min(lo, nums[j]);
                if (hi - lo > limit) {
                    break;
                }
                best = Math.max(best, j - i + 1);
            }
        }
        return best;
    }
}

2Optimal (sliding window + two monotonic deques)

TimeO(n)Each index is pushed into and popped from each deque at most once, and left only moves forward.
SpaceO(n)The deques can hold up to n indices (for example, on a strictly increasing array the min deque keeps everything).

Slide a window [left, right]. Keep a deque of indices whose values are decreasing (its front is the window max) and another whose values are increasing (its front is the window min). When a new element arrives, pop from the back of each deque every index it dominates, then push it. While max - min exceeds the limit, move left forward and drop deque fronts that fell out of the window. Each window that survives is valid, so record its length.

  1. left = 0, best = 0; maxQ and minQ are empty deques of indices.
  2. For each right: pop from maxQ's back while its value < nums[right], then push right; pop from minQ's back while its value > nums[right], then push right.
  3. While nums[maxQ.front] - nums[minQ.front] > limit: left++, and pop each deque's front if it is now < left.
  4. best = max(best, right - left + 1). Return best.
class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxQ = new ArrayDeque<>(); // values decreasing
        Deque<Integer> minQ = new ArrayDeque<>(); // values increasing
        int left = 0, best = 0;
        for (int right = 0; right < nums.length; right++) {
            while (!maxQ.isEmpty() && nums[maxQ.peekLast()] < nums[right]) maxQ.pollLast();
            maxQ.addLast(right);
            while (!minQ.isEmpty() && nums[minQ.peekLast()] > nums[right]) minQ.pollLast();
            minQ.addLast(right);
            while (nums[maxQ.peekFirst()] - nums[minQ.peekFirst()] > limit) {
                left++;
                if (maxQ.peekFirst() < left) maxQ.pollFirst();
                if (minQ.peekFirst() < left) minQ.pollFirst();
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Edge cases to test

  • A single element: the answer is 1
  • limit = 0: the longest run of equal values
  • A limit so large that the whole array qualifies
  • Strictly increasing or decreasing input, where the oldest element is always the one to drop

Hints

Hint 1

A window is valid exactly when max(window) - min(window) <= limit. Every pair inside then also satisfies the limit.

Hint 2

If a window is invalid, every larger window containing it is invalid too, so a sliding window works: grow on the right, shrink on the left.

Hint 3

The hard part is the window's max and min as the left edge moves. Two monotonic deques (one decreasing, one increasing) give both in O(1).

FAQ

What is the best time complexity for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?

Optimal (sliding window + two monotonic deques) runs in O(n) time and O(n) extra space. Each index is pushed into and popped from each deque at most once, and left only moves forward.

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

It is a arrays & hashing problem that uses the sliding window · variable pattern. Other problems with the same pattern: Minimum Size Subarray Sum, Count of Subarrays with Product Less Than K, Longest Repeating Character Replacement.

Is there a brute force solution for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?

Yes. Brute force takes O(n²) time and O(1) space. Fix each start index and extend the window to the right while tracking its running max and min.

Which edge cases should I test for Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?

A single element: the answer is 1; limit = 0: the longest run of equal values; A limit so large that the whole array qualifies; Strictly increasing or decreasing input, where the oldest element is always the one to drop.