LC-1438 Medium LeetCode

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

Array Queue Sliding Window Heap (Priority Queue) Ordered Set Monotonic Queue

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 57% Topics: Array, Queue, Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min Stacks & Queues 11 min Sliding Window 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

import collections


class Solution(object):
    def longestSubarray(self, nums, limit):
        """
        :type nums: List[int]
        :type limit: int
        :rtype: int
        """
        max_dq, min_dq = collections.deque(), collections.deque()
        left = 0
        for right, num in enumerate(nums):
            while max_dq and nums[max_dq[-1]] <= num:
                max_dq.pop()
            max_dq.append(right)
            while min_dq and nums[min_dq[-1]] >= num:
                min_dq.pop()
            min_dq.append(right)
            if nums[max_dq[0]]-nums[min_dq[0]] > limit:
                if max_dq[0] == left:
                    max_dq.popleft()
                if min_dq[0] == left:
                    min_dq.popleft()
                left += 1  # advance left by one to not count in result
        return len(nums)-left


# Time:  O(n)
# Space: O(n)
import collections


class Solution2(object):
    def longestSubarray(self, nums, limit):
        """
        :type nums: List[int]
        :type limit: int
        :rtype: int
        """
        max_dq, min_dq = collections.deque(), collections.deque()
        result, left = 0, 0
        for right, num in enumerate(nums):
            while max_dq and nums[max_dq[-1]] <= num:
                max_dq.pop()
            max_dq.append(right)
            while min_dq and nums[min_dq[-1]] >= num:
                min_dq.pop()
            min_dq.append(right)
            while nums[max_dq[0]]-nums[min_dq[0]] > limit:  # both always exist "right" element
                if max_dq[0] == left:
                    max_dq.popleft()
                if min_dq[0] == left:
                    min_dq.popleft()
                left += 1
            result = max(result, right-left+1)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT