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

XXX. Longest Subarray with Limit

Sliding Window

Heap

Problem Statement:

Given an array of integers nums and an integer limit, return the size of the longest contiguous subarray such that the absolute difference between the maximum and minimum element in the subarray is less than or equal to limit.

Algorithm:

The solution uses a sliding window combined with two heaps (a max heap for the maximum value and a min heap for the minimum value in the window):

1. Maintain two heaps:
   • Max heap: Tracks the maximum element in the current window.
   • Min heap: Tracks the minimum element in the current window.
2. Expand the window by adding elements to the heaps and check if the absolute difference between the maximum and minimum exceeds limit.
3. If the condition is violated, shrink the window by moving the left pointer and remove elements from the heaps that are no longer in the window.
4. Update the length of the longest valid subarray during each iteration.

Complexity:

Time Complexity: O(n log n), where n is the length of the array. Each insertion and deletion from the heaps takes O(log n).
Space Complexity: O(n), for the heaps.

Java Implementation:

import java.util.PriorityQueue;
import java.util.Comparator;

public class Solution {
    public int longestSubarray(int[] nums, int limit) {
        PriorityQueue maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        PriorityQueue minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        int left = 0, maxLength = 0;

        for (int right = 0; right < nums.length; ++right) {
            maxHeap.offer(new int[] { nums[right], right });
            minHeap.offer(new int[] { nums[right], right });

            // Check if the absolute difference between the max and min exceeds the limit
            while (maxHeap.peek()[0] - minHeap.peek()[0] > limit) {
                // Move the left pointer to exclude the violating element
                left = Math.min(maxHeap.peek()[1], minHeap.peek()[1]) + 1;

                // Remove elements outside the current window
                while (maxHeap.peek()[1] < left) 
                    maxHeap.poll();
                while (minHeap.peek()[1] < left) 
                    minHeap.poll();
            }

            // Update the maximum length of the valid subarray
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}