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

Description

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.

Solutions

Solution 1: Ordered Set + Sliding Window

This solution uses an ordered set (like SortedList in Python or TreeMap in Java) and a sliding window approach. The ordered set efficiently tracks the minimum and maximum values within the current window.

Algorithm:

1. Initialize an ordered set sl and variables ans (to store the maximum length) and j (left pointer of the sliding window).
2. Iterate through the nums array using a pointer i.
3. Add the current element nums[i] to the ordered set sl.
4. While the difference between the maximum and minimum elements in sl exceeds limit:
   • Remove nums[j] from sl.
   • Increment j (move the left boundary of the window).
5. Update ans with the maximum of ans and i - j + 1 (current window size).
6. Return ans.

Time Complexity: O(n log n) - Due to the ordered set operations (insertion and removal). Space Complexity: O(n) - The ordered set can store up to n elements in the worst case.

Solution 2: Binary Search + Sliding Window

This solution uses binary search to find the longest subarray length. For a given length k, it checks if a subarray of length k exists that satisfies the condition using two monotonic deques (one for min and one for max).

Algorithm:

1. Define a helper function check(k):
   • Initialize two deques, min_q and max_q, to track minimum and maximum elements within a window of size k.
   • Iterate through nums using a sliding window of size k.
   • Maintain min_q and max_q such that they contain indices of the minimum and maximum elements within the current window.
   • If the difference between the maximum and minimum elements in the window (nums[max_q[0]] - nums[min_q[0]]) is less than or equal to limit, return True.
   • Return False if no such window is found.
2. Perform a binary search on the possible lengths of subarrays (1 to len(nums)). check(k) determines whether a subarray of length k exists.
3. The final l from the binary search will be the length of the longest subarray.

Time Complexity: O(n log n) - Binary search iterates log n times, and check(k) takes O(n) time. Space Complexity: O(n) - The deques can store up to n elements each.

Solution 3: Sliding Window + Deque

This is an optimized solution that uses two deques to track the maximum and minimum values within the sliding window in linear time.

Algorithm:

1. Initialize two deques, maxq and minq, for storing indices of maximum and minimum elements respectively.
2. Initialize pointers l (left boundary) and r (right boundary) of the sliding window.
3. Iterate through nums using r:
   • While maxq is not empty and the element at the back of maxq is less than nums[r], pop from the back of maxq.
   • While minq is not empty and the element at the back of minq is greater than nums[r], pop from the back of minq.
   • Push r to the back of both maxq and minq.
   • If the difference between the maximum (nums[maxq[0]]) and minimum (nums[minq[0]]) elements exceeds limit:
     • Increment l.
     • Remove elements from the front of maxq and minq that are less than l.
4. Return n - l.

Time Complexity: O(n) - Each element is processed a constant number of times. Space Complexity: O(n) - The deques can store up to n elements in the worst case.

Code Examples (Python):

Solution 3 (Most efficient):

from collections import deque
 
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        maxq = deque()
        minq = deque()
        l, n = 0, len(nums)
        for r, x in enumerate(nums):
            while maxq and nums[maxq[-1]] < x:
                maxq.pop()
            while minq and nums[minq[-1]] > x:
                minq.pop()
            maxq.append(r)
            minq.append(r)
            if nums[maxq[0]] - nums[minq[0]] > limit:
                l += 1
                if maxq[0] < l:
                    maxq.popleft()
                if minq[0] < l:
                    minq.popleft()
        return n - l
 

The other solutions can be implemented similarly in other languages like Java, C++, and Go using appropriate data structures (e.g., TreeMap in Java, std::multiset in C++, container/heap in Go for Solution 1). Note that Solution 2 requires a custom deque implementation in some languages for optimal performance. Solution 3 provides the best time complexity.