< Back





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

We're asked to calculate the length of the longest subarray with an absolute difference between the
subarray's maximum and minimum elements.

From a previous problem, 239, we know that we can use a monotonic queue to
maintain the maximum across a subarray and remove the elements from the left side of the queue once
we exit a particular sliding window. Now we just do that for a minimum monotonic queue as well, and
our deciding factor to shrink the window will be if the difference between the maximum and the
minimum is greater than the limit.

In our solution, we maintain the queues in the beginning, and then add the most recent element. We
calculate the difference between the maximum and minimum elements in the current subarray. If the
difference is too great, if the leftmost element in each monotonic queue is the same as the leftmost
element in the sliding window, we pop it from each queue and shrink the window.

Finally, we calculate the answer by maintaining the maximum length of the window seen so far.

The solution is as follows:


  from collections import deque

  class Solution:
      def longestSubarray(self, nums: List[int], limit: int) -> int:
          increasing = deque()
          decreasing = deque()
          left = ans = 0

          for right in range(len(nums)):
              while increasing and increasing[-1] > nums[right]:
                  increasing.pop()
              while decreasing and decreasing[-1] < nums[right]:
                  decreasing.pop()

              increasing.append(nums[right])
              decreasing.append(nums[right])

              while decreasing[0] - increasing[0] > limit:
                  if nums[left] == decreasing[0]:
                      decreasing.popleft()
                  if nums[left] == increasing[0]:
                      increasing.popleft()
                  left += 1

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

          return ans


_ Time Complexity:

  O(n) - We inspect all values in the input array.

_ Space Complexity:

  O(n) - We maintain two monotonic queues.