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

Problem Statement

Given an integer array nums and an integer limit, return the maximum length of a continuous subarray such that the absolute difference between any two elements in this subarray is less than or equal to limit. The subarray must be non-empty.

Examples

Example 1:

• Input: nums = [1, 3, 6, 7, 9, 10], limit = 3
• Output: 3
• Explanation: Consider the [6, 7, 9] or [7, 9, 10] array. The absolute difference between any two elements in these subarrays is at most 3.

Example 2:

• Input: nums = [8, 2, 4, 10, 12], limit = 6
• Output: 3
• Explanation: The longest subarray is [8, 2, 4]. The absolute difference between any two elements in this subarray is at most 6.

Example 3:

• Input: nums = [1, 5, 9, 13, 14], limit = 4
• Output: 2
• Explanation: Consider the [1, 5], [5, 9], [9, 13] or [13, 14] array. The absolute difference between any two elements in these subarrays is at most 4.

Constraints:

• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁹
• 0 <= limit <= 10⁹

Solution

To solve this problem, we employ the Monotonic Queue technique to maintain two deques: one for tracking the maximum values and one for tracking the minimum values within the current window (subarray). The idea is to expand the window by moving the end pointer while checking if the difference between the maximum and minimum elements within this window exceeds the given limit. If it does, we shrink the window by moving the start pointer until the difference is within the limit. The length of the window is tracked to determine the maximum length of any valid subarray.

This approach works because the deques allow us to efficiently maintain and update the maximum and minimum values in the window, which enables us to check the conditions and adjust the window size in an optimal manner.

Step-by-Step Algorithm

1. Initialize Data Structures:

   • Create two empty deques: maxDeque for storing indices of elements in decreasing order (to track the maximum values) and minDeque for storing indices in increasing order (to track the minimum values).
   • Initialize two integer variables, start and maxLength, to 0. start will represent the beginning of the current subarray, and maxLength will store the maximum length of the valid subarray found.

2. Iterate Through the Array:

   • Use a for-loop with end iterating from 0 to nums.length - 1. end represents the end of the current subarray.

3. Update maxDeque:

   • While maxDeque is not empty and the value at nums[end] is greater than or equal to the value at nums[maxDeque.peekLast()], remove the last element from maxDeque.
     Reason: We want to keep the largest element at the front of maxDeque.
   • Add the current index end to maxDeque.

4. Update minDeque:

   • While minDeque is not empty and the value at nums[end] is less than or equal to the value at nums[minDeque.peekLast()], remove the last element from minDeque.
     Reason: We want to keep the smallest element at the front of minDeque.
   • Add the current index end to minDeque.

5. Check the Condition:

   • While the difference between the values at nums[maxDeque.peekFirst()] and nums[minDeque.peekFirst()] is greater than limit, perform the following steps:
     • Increment the start pointer by 1 to shrink the window from the left.
     • If maxDeque.peekFirst() is less than start, remove the first element from maxDeque. Reason: We are no longer considering elements before the start index.
     • If minDeque.peekFirst() is less than start, remove the first element from minDeque. Reason: We are no longer considering elements before the start index.

6. Update Maximum Length:

   • Calculate the length of the current window as end - start + 1.
   • Update maxLength to be the maximum of its current value and the current window length.

7. Return Result:

   • After completing the loop, return maxLength, which contains the length of the longest subarray satisfying the condition.

Algorithm Walkthrough

Let's walk through the algorithm with the input nums = [1, 3, 6, 7, 9, 10] and limit = 3.

1. Initial State:

   • maxDeque = [], minDeque = [], start = 0, maxLength = 0

2. Iteration 1 (end = 0):

   • Value: nums[0] = 1
   • Update maxDeque: maxDeque = [0] (1 is the only element, so it remains)
   • Update minDeque: minDeque = [0] (1 is the only element, so it remains)
   • Condition Check: The difference is nums[0] - nums[0] = 0 (within the limit)
   • Update maxLength: maxLength = max(0, 0 - 0 + 1) = 1

3. Iteration 2 (end = 1):

   • Value: nums[1] = 3
   • Update maxDeque: maxDeque = [1] (3 is greater than 1, so remove index 0)
   • Update minDeque: minDeque = [0, 1] (3 is greater than 1, so add index 1)
   • Condition Check: The difference is nums[1] - nums[0] = 3 - 1 = 2 (within the limit)
   • Update maxLength: maxLength = max(1, 1 - 0 + 1) = 2

4. Iteration 3 (end = 2):

   • Value: nums[2] = 6
   • Update maxDeque: maxDeque = [2] (6 is greater than 3, so remove index 1)
   • Update minDeque: minDeque = [0, 1, 2] (6 is greater than 3, so add index 2)
   • Condition Check: The difference is nums[2] - nums[0] = 6 - 1 = 5 (exceeds the limit)
   • Adjust start: Move start to 1 (increment by 1)
   • Update Deques: Remove 0 from minDeque since it is out of the window (minDeque = [1, 2])
   • Update maxLength: maxLength = max(2, 2 - 1 + 1) = 2

5. Iteration 4 (end = 3):

   • Value: nums[3] = 7
   • Update maxDeque: maxDeque = [3] (7 is greater than 6, so remove index 2)
   • Update minDeque: minDeque = [1, 2, 3] (7 is greater than 6, so add index 3)
   • Condition Check: The difference is nums[3] - nums[1] = 7 - 3 = 4 (exceeds the limit)
   • Adjust start: Move start to 2 (increment by 1)
   • Update Deques: Remove 1 from minDeque since it is out of the window (minDeque = [2, 3])
   • Update maxLength: maxLength = max(2, 3 - 2 + 1) = 2

6. Iteration 5 (end = 4):

   • Value: nums[4] = 9
   • Update maxDeque: maxDeque = [4] (9 is greater than 7, so remove index 3)
   • Update minDeque: minDeque = [2, 3, 4] (9 is greater than 7, so add index 4)
   • Condition Check: The difference is nums[4] - nums[2] = 9 - 6 = 3 (within the limit)
   • Update maxLength: maxLength = max(2, 4 - 2 + 1) = 3

7. Iteration 6 (end = 5):

   • Value: nums[5] = 10
   • Update maxDeque: maxDeque = [5] (10 is greater than 9, so remove index 4)
   • Update minDeque: minDeque = [2, 3, 4, 5] (10 is greater than 9, so add index 5)
   • Condition Check: The difference is nums[5] - nums[2] = 10 - 6 = 4 (exceeds the limit)
   • Adjust start: Move start to 3 (increment by 1)
   • Update Deques: Remove 2 from minDeque since it is out of the window (minDeque = [3, 4, 5])
   • Update maxLength: maxLength = max(3, 5 - 3 + 1) = 3

8. Final Result:

   • The algorithm completes, and maxLength = 3, which is the length of the longest subarray where the absolute difference between the maximum and minimum elements is within the given limit.

Code

import java.util.Deque;
import java.util.LinkedList;

class Solution {

  // Method to find the length of the longest subarray with an absolute difference less than or equal to limit
  public int longestSubarray(int[] nums, int limit) {
    // Monotonic queues to store the indices of elements in the order of minimum and maximum
    Deque<Integer> maxDeque = new LinkedList<>();
    Deque<Integer> minDeque = new LinkedList<>();

    int start = 0; // The starting index of the current subarray
    int maxLength = 0; // The maximum length of the subarray found so far

    for (int end = 0; end < nums.length; end++) {
      // Maintain the maxDeque to have the maximum value at the front
      while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] <= nums[end]) {
        maxDeque.pollLast();
      }
      maxDeque.addLast(end);

      // Maintain the minDeque to have the minimum value at the front
      while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= nums[end]) {
        minDeque.pollLast();
      }
      minDeque.addLast(end);

      // Check the difference between the current maximum and minimum in the window
      while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) {
        // If the difference exceeds the limit, move the start pointer to the right
        start++;
        // Remove the elements from the deque if they are out of the current window
        if (maxDeque.peekFirst() < start) {
          maxDeque.pollFirst();
        }
        if (minDeque.peekFirst() < start) {
          minDeque.pollFirst();
        }
      }

      // Update the maximum length found
      maxLength = Math.max(maxLength, end - start + 1);
    }

    return maxLength;
  }

  // Main method to test the solution with provided examples
  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] nums1 = { 1, 3, 6, 7, 9, 10 };
    int limit1 = 3;
    System.out.println("Output 1: " + solution.longestSubarray(nums1, limit1)); // Expected output: 3

    // Example 2
    int[] nums2 = { 8, 2, 4, 10, 12 };
    int limit2 = 6;
    System.out.println("Output 2: " + solution.longestSubarray(nums2, limit2)); // Expected output: 3

    // Example 3
    int[] nums3 = { 1, 5, 9, 13, 14 };
    int limit3 = 4;
    System.out.println("Output 3: " + solution.longestSubarray(nums3, limit3)); // Expected output: 2
  }
}

Complexity Analysis

Time Complexity

• The algorithm iterates through the array nums using the end pointer, and for each end, it may move the start pointer.
• Each element is added and removed from the maxDeque and minDeque at most once, leading to a time complexity of , where is the number of elements in the array.

So, the overall time complexity of the algorithm is .

Space Complexity

• The space complexity is due to the space required by the two deques (maxDeque and minDeque). In the worst case, both deques may store all the elements of the array if the window size covers the entire array.