#1438

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

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

Find the longest subarray with elements whose absolute difference is within a specified limit using a sliding window approach.

array queue sliding window heap priority queue ordered set

Problem Statement

You are given an array of integers, nums, and an integer, limit. Your task is to return the size of the longest non-empty subarray where the absolute difference between any two elements in this subarray is less than or equal to limit.

A sliding window approach is required to efficiently track the maximum and minimum values in the current window. By expanding and contracting the window based on the absolute difference condition, you can find the longest valid subarray.

Examples

Example 1

Input: nums = [8,2,4,7], limit = 4

Output: 2

All subarrays are: [8] with maximum absolute diff |8-8| = 0 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. [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

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

Example details omitted.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109
0 <= limit <= 109

Solution Approach

Sliding Window with Maximum and Minimum Tracking

Use a sliding window to maintain a dynamic range of numbers where the absolute difference between the maximum and minimum is within the given limit. As the window slides, track the maximum and minimum values using data structures like a deque or multiset, and adjust the window's size accordingly.

Efficient Window Expansion and Contraction

As the window expands to include new elements, check whether the difference between the maximum and minimum exceeds the limit. If it does, contract the window from the left side until the condition is met again. This allows the algorithm to process elements in O(n) time.

Using Deque or Multiset for Tracking

To maintain the maximum and minimum elements efficiently, use a deque (double-ended queue) or a multiset (in C++) to quickly access the current maximum and minimum values within the window. These structures allow you to keep the time complexity of updating the window within bounds.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) because each element is added and removed from the sliding window at most once. The space complexity is O(n) due to the additional space required for the data structures used to track the window's maximum and minimum values.

What Interviewers Usually Probe

Look for understanding of sliding window techniques.
Evaluate how efficiently the candidate handles window adjustments and tracking of max/min values.
Assess the ability to explain why O(n) time complexity is achievable.

Common Pitfalls or Variants

Common pitfalls

Failing to update the window correctly when the absolute difference exceeds the limit.
Using inefficient data structures for tracking max/min values, leading to suboptimal time complexity.
Not handling edge cases such as very small arrays or large limit values properly.

Follow-up variants

Allowing the subarray to contain negative numbers and adjusting the absolute difference condition.
Extending the problem to find the sum of elements in the longest subarray that meets the condition.
Modifying the condition to check for differences in specific positions within the subarray instead of all pairs.

FAQ

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

The best approach is using a sliding window technique that maintains the maximum and minimum values of the current subarray, expanding and contracting the window based on the absolute difference condition.

How do I handle large arrays efficiently for this problem?

For large arrays, you should use a sliding window approach with data structures like deques or multisets that allow for efficient tracking of the window's maximum and minimum values in O(1) time.

Why is the sliding window approach optimal for this problem?

The sliding window approach ensures that each element is processed only once, leading to an O(n) time complexity. This is much more efficient than checking every pair of elements directly.

What are some common mistakes in solving this problem?

Common mistakes include not correctly adjusting the window when the absolute difference exceeds the limit, and using inefficient data structures for tracking the max/min values.

How can GhostInterview help me solve problems like Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?

GhostInterview provides targeted practice on sliding window techniques and helps you master optimal data structures for maintaining dynamic ranges in problems like this.

terminal

Solution

Solution 1: Ordered Set + Sliding Window

We can enumerate each position as the right endpoint of the subarray, and find the leftmost left endpoint corresponding to it, such that the difference between the maximum and minimum values in the interval does not exceed $limit$. During the process, we use an ordered set to maintain the maximum and minimum values within the window.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        sl = SortedList()
        ans = j = 0
        for i, x in enumerate(nums):
            sl.add(x)
            while sl[-1] - sl[0] > limit:
                sl.remove(nums[j])
                j += 1
            ans = max(ans, i - j + 1)
        return ans

Solution 2: Binary Search + Sliding Window

We notice that if a subarray of length $k$ satisfies the condition, then a subarray of length $k' < k$ also satisfies the condition. This shows a monotonicity, therefore, we can use binary search to find the longest subarray that satisfies the condition.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        sl = SortedList()
        ans = j = 0
        for i, x in enumerate(nums):
            sl.add(x)
            while sl[-1] - sl[0] > limit:
                sl.remove(nums[j])
                j += 1
            ans = max(ans, i - j + 1)
        return ans

Solution 3: Sliding Window + Deque

We can use a deque to maintain the maximum and minimum values within the window. We maintain two deques, one for storing the indices of the maximum values and the other for the minimum values within the window. Define two pointers $l$ and $r$ to point to the left and right boundaries of the window, respectively.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        sl = SortedList()
        ans = j = 0
        for i, x in enumerate(nums):
            sl.add(x)
            while sl[-1] - sl[0] > limit:
                sl.remove(nums[j])
                j += 1
            ans = max(ans, i - j + 1)
        return ans

Continue Practicing

#1425 constrained subsequence sum #862 shortest subarray with sum at least k #2398 maximum number of robots within budget