We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

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

Difficulty: Medium

Problem 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.

Key Insights

  • We need to find the longest contiguous subarray where the maximum absolute difference between any two elements is bounded by limit.
  • A sliding window approach is appropriate, allowing us to efficiently check the conditions for the subarray.
  • We can use two deques (or a sorted data structure) to maintain the minimum and maximum values within the current window.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the nums array. Each element is processed at most twice. Space Complexity: O(n), for the space used by deques to maintain the minimum and maximum values.

Solution

We can use a sliding window approach with two deques to maintain the current minimum and maximum values in the window. As we expand the window to include new elements, we will check if the absolute difference between the maximum and minimum exceeds the limit. If it does, we will shrink the window from the left until the condition is satisfied again. At each valid window, we update the maximum length found.

Code Solutions

def longestSubarray(nums, limit):
    from collections import deque
    
    max_deque = deque()
    min_deque = deque()
    left = 0
    max_length = 0
    
    for right in range(len(nums)):
        while max_deque and nums[max_deque[-1]] <= nums[right]:
            max_deque.pop()
        max_deque.append(right)
        
        while min_deque and nums[min_deque[-1]] >= nums[right]:
            min_deque.pop()
        min_deque.append(right)
        
        while nums[max_deque[0]] - nums[min_deque[0]] > limit:
            left += 1
            if max_deque[0] < left:
                max_deque.popleft()
            if min_deque[0] < left:
                min_deque.popleft()
        
        max_length = max(max_length, right - left + 1)
    
    return max_length
← Back to All Questions