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

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.

Step by Step Implementation For Longest Continuous Subarray With Absolute Diff Less Than Or Equal To Limit

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int n = nums.length, res = 0, i = 0, j;
        for (j = 0; j < n; ++j) {
            limit -= Math.abs(nums[j] - nums[i]);
            while (i < j && limit < 0)
                limit += Math.abs(nums[j] - nums[i++]);
            res = Math.max(res, j - i + 1);
        }
        return res;
    }
}

def longestSubarray(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        left = 0
        right = 1
        ans = 1
        curr_max = nums[0]
        curr_min = nums[0]
        
        while right < n:
            curr_max = max(curr_max, nums[right])
            curr_min = min(curr_min, nums[right])
            
            if curr_max - curr_min <= limit:
                ans = max(ans, right - left + 1)
                right += 1
            else:
                curr_max = nums[left]
                curr_min = nums[left]
                left += 1
                right = left + 1
                
        return ans

var longestSubarray = function(nums, limit) {
    let longest = 0;
    let left = 0;
    
    for (let right = 0; right < nums.length; right++) {
        let min = Math.min(...nums.slice(left, right + 1)); // inclusive
        let max = Math.max(...nums.slice(left, right + 1));
        
        if (max - min <= limit) {
            longest = Math.max(longest, right - left + 1);
        } else {
            while (max - min > limit) {
                let removed = nums[left];
                left++;
                
                if (removed === min) {
                    min = Math.min(...nums.slice(left, right + 1));
                } else if (removed === max) {
                    max = Math.max(...nums.slice(left, right + 1));
                }
            }
        }
    }
    
    return longest;
};

class Solution {
public:
    int longestSubarray(vector& nums, int limit) {
        int n = nums.size();
        int ans = 1;
        for (int i = 0; i < n; ++i) {
            int mx = nums[i], mn = nums[i];
            for (int j = i + 1; j < n; ++j) {
                mx = max(mx, nums[j]);
                mn = min(mn, nums[j]);
                if (mx - mn <= limit) {
                    ans = max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
};

public int LongestSubarray(int[] nums, int limit) { // edge case if (nums.Length == 0) return 0; int maxLength = 1; int left = 0; int right = 1; // initialize min and max value for the subarray int min = nums[left]; int max = nums[left]; // loop through the array while (right < nums.Length) { // update min and max value for the subarray min = Math.Min(min, nums[right]); max = Math.Max(max, nums[right]); // check if the absolute difference between min and max is less than or equal to limit if (max - min <= limit) { // update max length maxLength = Math.Max(maxLength, right - left + 1); // move to the next element right++; } else { // move left pointer to the next element left++; // if left pointer is at the same position as right pointer, move right pointer to the next element if (left == right) right++; } } return maxLength; }