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.

For example: 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.

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.

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

Longest Subarray With Absolute Difference Constraint

Problem Description

Given an array of integers nums and an integer limit, the task is to find 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

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

Explanation: The longest subarray meeting the constraint is [2, 4] or [4, 7] with length 2. The absolute difference between any two numbers in these subarrays is at most 4.

Brute Force Solution

The brute force solution involves checking every possible subarray and verifying if it satisfies the given condition. For each subarray, we find the maximum and minimum elements and check if their absolute difference is within the given limit.

def longest_subarray_brute_force(nums, limit):
    n = len(nums)
    max_len = 0
    for i in range(n):
        for j in range(i, n):
            subarray = nums[i:j+1]
            if not subarray:
                continue
            max_val = max(subarray)
            min_val = min(subarray)
            if max_val - min_val <= limit:
                max_len = max(max_len, len(subarray))
    return max_len

Optimal Solution (Sliding Window with Monotonic Deque)

We can use a sliding window approach combined with two monotonic deques (one for maintaining the maximum element and one for maintaining the minimum element within the window). This helps us efficiently track the maximum absolute difference in the current window.

from collections import deque

def longest_subarray_optimal(nums, limit):
    max_deque = deque()
    min_deque = deque()
    left = 0
    max_len = 0
    
    for right in range(len(nums)):
        # Maintain max_deque
        while max_deque and nums[right] >= nums[max_deque[-1]]:
            max_deque.pop()
        max_deque.append(right)
        
        # Maintain min_deque
        while min_deque and nums[right] <= nums[min_deque[-1]]:
            min_deque.pop()
        min_deque.append(right)
        
        # Shrink window if necessary
        while nums[max_deque[0]] - nums[min_deque[0]] > limit:
            if left == max_deque[0]:
                max_deque.popleft()
            if left == min_deque[0]:
                min_deque.popleft()
            left += 1
        
        max_len = max(max_len, right - left + 1)
        
    return max_len

Big(O) Run-time Analysis

• Brute Force: The brute force solution has a time complexity of O(n^2) due to nested loops for generating all subarrays and O(n) for finding min/max in each subarray, resulting in O(n^3) overall. Optimizing min/max to O(1) doesn't change the O(n^2) term.
• Optimal Solution: The optimal solution using a sliding window and monotonic deques has a time complexity of O(n). Each element is visited at most twice (once by the right pointer and once by the left pointer), and deque operations (append/pop) take O(1) time on average.

Big(O) Space Usage Analysis

• Brute Force: The brute force solution has a space complexity of O(1) as it only uses a few variables to store the maximum length and temporary values.
• Optimal Solution: The optimal solution has a space complexity of O(n) in the worst case because the monotonic deques could potentially store all the indices of the array if the array is monotonically increasing or decreasing.

Edge Cases

1. Empty Array: If the input array is empty, the function should return 0, as there are no subarrays.
2. Single Element Array: If the input array contains only one element, the function should return 1, as the subarray containing that single element will always satisfy the condition.
3. Limit is 0: When the limit is 0, all elements in the subarray must be equal. The algorithm should correctly identify the longest subarray with identical elements.
4. Large Limit: If the limit is very large (e.g., greater than the difference between the maximum and minimum values in the entire array), the function should return the length of the entire array.
5. Negative Numbers: The algorithm should work correctly with negative numbers in the input array.

# Examples of edge cases
print(longest_subarray_optimal([], 5))  # Output: 0
print(longest_subarray_optimal([5], 5))  # Output: 1
print(longest_subarray_optimal([1, 1, 1, 1], 0))  # Output: 4
print(longest_subarray_optimal([1, 2, 3, 4, 5], 100))  # Output: 5
print(longest_subarray_optimal([-1, -5, -3, -2], 2))  # Output: 2