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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 1549

Difficulty: Medium

Paid? No

Companies: Uber, Capital One, Google, Amazon, Visa, eBay, Meta, PhonePe, Nutanax, Microsoft

Problem Description

Given an array of integers nums and an integer limit, find the length of the longest non-empty subarray such that the absolute difference between any two elements in this subarray is less than or equal to limit.

Key Insights

  • Use a sliding window approach to efficiently find the longest valid subarray.
  • Maintain the current window's minimum and maximum values using two monotonic deques.
  • One deque (minDeque) will keep track of elements in increasing order to quickly access the minimum.
  • The other deque (maxDeque) will track elements in decreasing order to quickly access the maximum.
  • Slide the right pointer to expand the window and when the condition (max - min > limit) is violated, move the left pointer to shrink the window.
  • The deques are updated by removing indices that are no longer in the window or are not useful for maintaining the monotonic order.

Space and Time Complexity

Time Complexity: O(n) – Each element is processed at most twice (once when added and once when removed from the window). Space Complexity: O(n) – In the worst case, the deques may hold all the elements.

Solution

We use the sliding window technique with two deques to store indices for the current window's maximum and minimum values. As we iterate through nums with a right pointer, we update:

  1. The maxDeque by removing elements from the back that are less than the current element.
  2. The minDeque by removing elements from the back that are greater than the current element. Then, if the current window (from left to right) does not satisfy the condition (i.e., the difference between the front values of maxDeque and minDeque is greater than limit), we increment the left pointer and update the deques by discarding indices that fall out of the window. The maximum window length encountered is the answer.

Code Solutions

from collections import deque

def longestSubarray(nums, limit):
    maxDeque = deque()  # stores indices for the maximum values
    minDeque = deque()  # stores indices for the minimum values
    left = 0
    maxLength = 0
    
    # Iterate over each index with right pointer
    for right in range(len(nums)):
        # Maintain decreasing order in maxDeque
        while maxDeque and nums[right] > nums[maxDeque[-1]]:
            maxDeque.pop()
        maxDeque.append(right)
        
        # Maintain increasing order in minDeque
        while minDeque and nums[right] < nums[minDeque[-1]]:
            minDeque.pop()
        minDeque.append(right)
        
        # If window is invalid, shrink from the left
        while nums[maxDeque[0]] - nums[minDeque[0]] > limit:
            # Move the left pointer forward and remove indices if they are out of the new window
            if maxDeque[0] == left:
                maxDeque.popleft()
            if minDeque[0] == left:
                minDeque.popleft()
            left += 1
        
        # Update maxLength with the valid window size
        maxLength = max(maxLength, right - left + 1)
    
    return maxLength

# Example usage:
print(longestSubarray([8,2,4,7], 4))
← Back to All Questions