Longest Continuous Subarray With Absolute Diff Less Than Or Equal To Limit - Leetcode Solution

Problem statement:

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: [8] with maximum absolute diff |8-8| = 0 <= 4. [8,2] with maximum absolute diff |8-2| = 6 > 4. [8,2,4] with maximum absolute diff |8-2| = 6 > 4 and |2-4| = 2 <= 4. [8,2,4,7] with maximum absolute diff |8-2| = 6 > 4 and |2-4| = 2 <= 4 and |4-7| = 3 <= 4.

Solution:

One of the ways to solve this problem is to use a sliding window approach. We will iterate through the array and keep track of two pointers, i and j, which represent the start and end of the subarray. We will also keep track of the minimum and maximum elements in the subarray using a minHeap and a maxHeap. The absolute difference between the two is the current limit.

We start by moving the end pointer j, while keeping track of the minimum and maximum elements in the subarray. If the absolute difference between them is greater than the limit, we move the start pointer i and remove the corresponding element from the minHeap and maxHeap. We continue this process until the absolute difference is less than or equal to the limit. At each step, we update the maximum length of the subarray.

Algorithm:

1. Initialize the start pointer i to 0, the length of the array n to the end pointer j to 0, and two heaps (minHeap and maxHeap) to store the minimum and maximum elements of the subarray.
2. Iterate through the array from j = 0 to j = n-1: a. Add nums[j] to the minHeap and maxHeap. b. If the absolute difference between the minimum and maximum elements in the minHeap and maxHeap is greater than limit: i. Remove nums[i] from both heaps. ii. Increment i by 1. c. Update the maximum length of the subarray.
3. Return the maximum length.

Code in Python:

import heapq

def longestSubarray(nums, limit): i = 0 maxLen = 0 minHeap, maxHeap = [], [] for j in range(len(nums)): heapq.heappush(minHeap, nums[j]) heapq.heappush(maxHeap, -nums[j]) while abs(maxHeap[0]) - minHeap[0] > limit: if abs(maxHeap[0]) == nums[i]: heapq.heappop(maxHeap) if minHeap[0] == nums[i]: heapq.heappop(minHeap) i += 1 maxLen = max(maxLen, j - i + 1) return maxLen

Time Complexity:

The time complexity of the algorithm is O(n log n), where n is the length of the input array. It is due to the usage of heaps to store the minimum and maximum elements of the subarray. The while loop inside the main loop runs at most n times, and each push and pop operation on the heaps takes logarithmic time.

1