Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit — LeetCode 1438 Python Solution

MediumQueueArrayOrdered SetSliding WindowMonotonic QueueHeap (Priority Queue)

Problem: #1438
Pattern: Sliding Window
Reading time: 3 min
Source: leetcode.com

The problem

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.

Example

Input: nums = [8,2,4,7], limit = 4
Output: 2
Explanation: All subarrays are:

Python solution

Python

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        sl = SortedList()
        ans = j = 0
        for i, x in enumerate(nums):
            sl.add(x)
            while sl[-1] - sl[0] > limit:
                sl.remove(nums[j])
                j += 1
            ans = max(ans, i - j + 1)
        return ans

Complexity

Measure	Complexity
Time	O(n \log n)
Space	O(n) auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Sliding Window.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?: LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit is rated Medium on LeetCode.
What is the time complexity of LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?: The Python solution on this page runs in O(n \log n).
What is the space complexity of LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit cover?: LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit is tagged Queue, Array, Ordered Set, Sliding Window, Monotonic Queue and Heap (Priority Queue) on LeetCode.