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

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

What is this problem about?

This array problem asks you to find the length of the longest contiguous subarray where the absolute difference between any two elements inside that subarray does not exceed a given limit. For example, if your subarray is [2, 4, 7, 2] and the limit is 5, this is a valid subarray because the maximum difference is $|7 - 2| = 5$, which is $\le 5$.

Why is this asked in interviews?

This question is widely used by top-tier tech companies because it tests a candidate's ability to optimize a Sliding Window problem. A brute-force solution checking every subarray takes $O(N^3)$ time, while a basic sliding window checking min/max at every step takes $O(N^2)$. Interviewers want to see if you can utilize advanced data structures, like Monotonic Queues, to achieve a highly optimized $O(N)$ solution.

Algorithmic pattern used

The optimal approach is a Sliding Window combined with two Monotonic Queues. As you expand the window by moving the right pointer, you add elements into a decreasing queue (to keep track of the maximum value) and an increasing queue (to keep track of the minimum value). If the difference between the front of the max-queue and the front of the min-queue exceeds the limit, you shrink the window by moving the left pointer, popping elements from the queues if they fall out of the window.

Example explanation

Let array be [8, 2, 4, 7] and limit = 4.

• right = 0 (8): MaxQueue=[8], MinQueue=[8]. Diff = 0. Valid. MaxLen = 1.
• right = 1 (2): MaxQueue=[8, 2], MinQueue=[2]. Diff = 8-2 = 6. Exceeds limit! We must move left. left becomes 1. MaxQueue pops 8. Window is now [2].
• right = 2 (4): MaxQueue=[4], MinQueue=[2, 4]. Diff = 4-2 = 2. Valid. MaxLen = 2.
• right = 3 (7): MaxQueue=[7], MinQueue=[2, 4, 7]. Diff = 7-2 = 5. Exceeds limit! Move left to 2. MinQueue pops 2. Window is now [4, 7]. Diff = 7-4 = 3. Valid. MaxLen remains 2. The maximum length is 2.

Common mistakes candidates make

A major pitfall is trying to find the minimum and maximum of the current window using a linear scan or standard Math.max() over the array slice on every iteration. This inflates the time complexity and leads to Time Limit Exceeded errors on large datasets. Another mistake is using a simple priority queue (heap) which gives $O(N \log N)$ time, instead of Monotonic Queues (Deq) which guarantee amortized $O(1)$ operations per element.

Interview preparation tip

To master the Longest Continuous Subarray with Limit problem, thoroughly practice implementing Double-Ended Queues (Deque) to maintain monotonic sequences. Understand exactly why a decreasing deque keeps the maximum element at the front: as you insert a new number, you kick out all smaller numbers before it, because they will never be the maximum in any future window that includes the new, larger number.