Medium

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

LAB

Return the longest contiguous subarray length whose maximum and minimum differ by at most limit.

EXAMPLES

Example 1

Input
{
  "nums": [
    8,
    2,
    4,
    7
  ],
  "limit": 4
}

Output
2

FUNCTION SHAPE

nums: intArraylimit: int→int

SOLUTION NOTE

Classic sliding window + SortedList. window[0] is min, window[-1] is max. Shrink from left when constraint violated.

Reveal reference solution +

pythonREFERENCE

def longestSubarray(self, nums: List[int], limit: int) -> int:
    from sortedcontainers import SortedList

    window = SortedList()
    left = 0
    result = 0

    for right in range(len(nums)):
        window.add(nums[right])

        # Shrink window while invalid
        while window[-1] - window[0] > limit:
            window.remove(nums[left])
            left += 1

        result = max(result, right - left + 1)

    return result

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗