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

The optimal approach uses a sliding window with two monotonic deques to maintain the current maximum and minimum values. This allows checking the constraint max − min ≤ limit in constant time while expanding and shrinking the window. Each element is processed once, resulting in O(n) time complexity and O(n) space.

What data structure is used in Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?

The most efficient solution uses two monotonic deques to track the maximum and minimum values within the sliding window. Another common implementation uses an ordered map such as TreeMap to keep elements sorted and retrieve the smallest and largest values quickly.

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

The optimal monotonic deque solution runs in O(n) time because every element is added and removed from the deques at most once. Space complexity is O(n) in the worst case for the deques. An alternative TreeMap solution takes O(n log n) time due to ordered map insertions and deletions.

Description Hints 2 Solution Video 10:23

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

Q: Is Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit easy or hard?

The problem is generally rated Medium difficulty. The sliding window idea is straightforward, but efficiently maintaining both the minimum and maximum inside the window requires understanding monotonic queues, which many candidates encounter for the first time in this type of problem.

Q: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit Python/Java solution

Most implementations use the sliding window with monotonic deque pattern. Python uses collections.deque, Java typically uses ArrayDeque, and C++ uses deque from the STL. The algorithm maintains decreasing and increasing deques to track the current window's maximum and minimum values.

Q: How to solve Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit in O(n)?

Use a sliding window with two deques: one decreasing deque for maximum values and one increasing deque for minimum values. Expand the right pointer while inserting elements into both structures. If the difference between the deque fronts exceeds the limit, move the left pointer and remove outdated elements. This keeps max and min queries O(1), producing an overall O(n) algorithm.

Q: Is Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit asked at Google/Amazon/Meta?

Sliding window problems with min/max constraints appear frequently in interviews at companies such as Amazon, Google, and Meta. Variants of this problem test your ability to maintain dynamic window statistics using data structures like monotonic queues or ordered maps.

Medium58.1% acceptance15 companies

Given an array of integers 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.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
0 <= limit <= 10⁹

Asked at 15 companies

Uber Moloco Capital One Visa PhonePe eBay Sumo Logic

Google Amazon Salesforce NVIDIA Microsoft

+3 more

Meta Yandex Bloomberg

Topics

Hints open one at a time

Hint 1

Use a sliding window approach keeping the maximum and minimum value using a data structure like a multiset from STL in C++.

Hint 2

More specifically, use the two pointer technique, moving the right pointer as far as possible to the right until the subarray is not valid (maxValue - minValue > limit), then moving the left pointer until the subarray is valid again (maxValue - minValue <= limit). Keep repeating this process.

10:23

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution