medium Continuous Subarrays

Problem Statement

You are given a 0-indexed array of integers called nums. A subarray of num is called continuous if the following condition is met:

• consider i, i + 1, ..., j be the indices in the subarray. Then, for each pair of indices i <= i1, i2 <= j, 0 <= |nums[i1] - nums[i2]| <= 2.

Return the total number of continuous subarrays within nums.

A subarray is defined as any contiguous, non-empty sequence of elements within an array.

Examples

Example 1:

• Input: nums = [1, 2, 2, 13, 1]
• Expected Output: 8
• Justification: The continuous subarrays are [1], [2], [2], [13], [1], [1, 2], [2, 2], and [1, 2, 2].

Example 2:

• Input: nums = [3, 3, 4, 2]
• Expected Output: 10
• Justification: The continuous subarrays are [3], [3], [4], [2], [3, 3], [3, 4], [4, 2], [3, 3, 4], [3, 4, 2], and [3, 3, 4, 2].

Example 3:

• Input: nums = [5, 17, 35, 26, 5]
• Expected Output: 5
• Justification: The continuous subarrays are [5], [17], [35], [26], and [5].

Constraints:

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

Solution

This problem is similar to the "Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit" problem, but with a twist. In this case, the limit is fixed at 2, meaning that we must find all subarrays where the maximum difference between any two elements does not exceed 2. The goal is to count the total number of such continuous subarrays within the given array.

To solve this problem, we use a sliding window approach combined with two deques (double-ended queues) to efficiently track the minimum and maximum values within the current subarray. The deques allow us to maintain the order of elements in a way that makes it easy to adjust the window size dynamically by moving the left pointer whenever the difference between the maximum and minimum values exceeds 2. By counting all valid subarrays ending at each position, we can calculate the total number of continuous subarrays that satisfy the condition.

Step-by-Step Algorithm

1. Initialize Deques and Pointers:

   • Start by creating two empty deques, maxQ and minQ. These will help us keep track of the maximum and minimum values within the current subarray.
   • Initialize two pointers: left to 0 (start of the subarray) and right to 0 (end of the subarray).
   • Also, initialize ans to 0, which will store the total count of continuous subarrays, and n to the length of the input array nums.

2. Iterate Over the Array:

   • Begin a loop with the right pointer moving from the start to the end of the array.
   • For each element at position right, perform the following steps:

3. Maintain Decreasing Order in maxQ:

   • While maxQ is not empty and the last element in maxQ is less than the current element (nums[right]), remove elements from the back of maxQ.
   • This step ensures that maxQ always contains elements in decreasing order from front to back, with the maximum value at the front.

4. Maintain Increasing Order in minQ:

   • Similarly, while minQ is not empty and the last element in minQ is greater than the current element (nums[right]), remove elements from the back of minQ.
   • This step ensures that minQ always contains elements in increasing order from front to back, with the minimum value at the front.

5. Add Current Element to Deques:

   • Add the current element (nums[right]) to both maxQ and minQ.

6. Adjust the left Pointer:

   • While the difference between the maximum value (maxQ.peekFirst()) and the minimum value (minQ.peekFirst()) is greater than 2:
     • If the element at the left pointer is equal to the first element in maxQ, remove it from maxQ.
     • If the element at the left pointer is equal to the first element in minQ, remove it from minQ.
     • Move the left pointer to the right by incrementing left.
     • This step ensures that the subarray always satisfies the condition max - min <= 2.

7. Count Valid Subarrays:

   • Add the number of valid subarrays ending at the right pointer to ans. The number of such subarrays is right - left + 1.

8. Continue Until End of Array:

   • Continue this process until the right pointer has iterated through the entire array.

9. Return the Result:

   • Finally, return ans, which contains the total number of valid continuous subarrays.

Algorithm Walkthrough

Let's consider the Input: nums = [1, 2, 2, 13, 1]

1. Initialization:

   • left = 0, right = 0, ans = 0.
   • maxQ = [], minQ = [].

2. Iteration 1 (right = 0):

   • Current element: nums[0] = 1.
   • maxQ and minQ are empty. So, add 1 to both maxQ and minQ.
   • Since maxQ.peekFirst() - minQ.peekFirst() = 1 - 1 = 0 (which is ≤ 2), the subarray [1] is valid.
   • Valid subarrays count: 1 (for the subarray [1]).
   • Update ans = ans + right - left + 1 = 0 + 0 + 0 + 1 = 1.
   • maxQ = [1], minQ = [1].

3. Iteration 2 (right = 1):

   • Current element: nums[1] = 2.
   • Maintain maxQ: Remove 1 from maxQ (since 1 < 2), then add 2 to maxQ.
   • Maintain minQ: Add 2 to minQ.
   • Since maxQ.peekFirst() - minQ.peekFirst() = 2 - 1 = 1 (which is ≤ 2), the subarrays [2] and [1, 2] are valid.
   • Valid subarrays count: right - left + 1 = 1 - 0 + 1 = 2 (for the subarrays [2] and [1, 2]).
   • Update ans = 3.
   • maxQ = [2], minQ = [1, 2].

4. Iteration 3 (right = 2):

   • Current element: nums[2] = 2.
   • Maintain maxQ: Add 2 to maxQ.
   • Maintain minQ: Add 2 to minQ.
   • Since maxQ.peekFirst() - minQ.peekFirst() = 2 - 1 = 1 (which is ≤ 2), the subarrays [2], [2, 2], and [1, 2, 2] are valid.
   • Valid subarrays count: right - left + 1 = 2 - 0 + 1 = 3 (for the subarrays [2], [2, 2], and [1, 2, 2]).
   • Update ans = 6.
   • maxQ = [2, 2], minQ = [1, 2, 2].

5. Iteration 4 (right = 3):

   • Current element: nums[3] = 13.
   • Maintain maxQ: Remove 2 and 2 from maxQ (since 2 < 13), then add 13 to maxQ.
   • Maintain minQ: Add 13 to minQ.
   • Since maxQ.peekFirst() - minQ.peekFirst() = 13 - 1 = 12 (which is > 2), we adjust the left pointer:
     • Move left to 1, remove 1 from minQ.
     • Since 13 - 2 = 11 (which is still > 2), move left to 2, remove 2 from minQ.
     • Since 13 - 2 = 11 (which is still > 2), move left to 3, remove 2 from minQ.
   • Now, with left = 3, maxQ.peekFirst() - minQ.peekFirst() = 13 - 13 = 0 (which is ≤ 2), the subarray [13] is valid.
   • Valid subarrays count: right - left + 1 = 3 - 3 + 1 = 1 (for the subarray [13]).
   • Update ans = 7.
   • maxQ = [13], minQ = [13].

6. Iteration 5 (right = 4):

   • Current element: nums[4] = 1.
   • Maintain maxQ: Add 1 to maxQ.
   • Maintain minQ: Remove 13 from minQ, add 1 to minQ.
   • Since maxQ.peekFirst() - minQ.peekFirst() = 13 - 1 = 12 (which is > 2), adjust the left pointer:
     • Move left to 4, remove 13 from maxQ.
   • Now, with left = 4, maxQ.peekFirst() - minQ.peekFirst() = 1 - 1 = 0 (which is ≤ 2), the subarray [1] is valid.
   • Valid subarrays count: right - left + 1 = 4 - 4 + 1 = 1 (for the subarray [1]).
   • Update ans = 8.
   • maxQ = [1], minQ = [1].

7. End of Loop:

   • The loop ends with right reaching the end of the array.
   • The final answer is 8, representing the total number of valid continuous subarrays.

Code

import java.util.*;

class Solution {

  Deque<Integer> maxQ;
  Deque<Integer> minQ;

  public int getMaxInSubarray() {
    // Return -1 if max queue is empty, otherwise return the first element
    return maxQ.size() == 0 ? -1 : maxQ.peekFirst();
  }

  public int getMinInSubarray() {
    // Return -1 if min queue is empty, otherwise return the first element
    return minQ.size() == 0 ? -1 : minQ.peekFirst();
  }

  public long continuousSubarrays(int[] nums) {
    minQ = new ArrayDeque<>();
    maxQ = new ArrayDeque<>();

    int left = 0; // Left pointer representing the start of the subarray
    int right = 0; // Right pointer representing the end of the subarray
    long ans = 0;
    int n = nums.length;

    // Iterate through the array using the right pointer
    while (right < n) {
      // Ensure maxQ contains elements in decreasing order from front to back
      while (maxQ.size() > 0 && maxQ.peekLast() < nums[right]) {
        maxQ.removeLast();
      }
      // Ensure minQ contains elements in increasing order from front to back
      while (minQ.size() > 0 && minQ.peekLast() > nums[right]) {
        minQ.removeLast();
      }
      // Add the current element to both maxQ and minQ
      maxQ.addLast(nums[right]);
      minQ.addLast(nums[right]);

      // Adjust the left pointer to maintain the subarray's condition
      while (getMaxInSubarray() - getMinInSubarray() > 2) {
        // Remove the element at the left pointer if it's the first in maxQ or minQ
        if (maxQ.size() > 0 && maxQ.peekFirst() == nums[left]) {
          maxQ.removeFirst();
        }
        if (minQ.size() > 0 && minQ.peekFirst() == nums[left]) {
          minQ.removeFirst();
        }
        left++;
      }

      // Add the number of subarrays ending at right to the answer
      ans += right - left + 1;
      right++;
    }
    return ans;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Test case 1
    int[] nums1 = { 1, 2, 2, 13, 1 };
    System.out.println("Example 1: " + solution.continuousSubarrays(nums1));

    // Test case 2
    int[] nums2 = { 3, 3, 4, 2 };
    System.out.println("Example 2: " + solution.continuousSubarrays(nums2));

    // Test case 3
    int[] nums3 = { 5, 17, 35, 26, 5 };
    System.out.println("Example 3: " + solution.continuousSubarrays(nums3));
  }
}

Complexity Analysis

Time Complexity

• The time complexity of this algorithm is , where n is the length of the input array nums.
• The right pointer traverses each element of the array exactly once.
• The left pointer may also traverse each element once, but since every element is added and removed from the deque at most once, the operations inside the loops (adding and removing elements from the deque) are amortized operations.
• Therefore, the overall time complexity remains .

Space Complexity

• The space complexity of the algorithm is because we use two deques (maxQ and minQ) to store elements from the array. In the worst case, all elements could be stored in these deques, leading to a space complexity proportional to the size of the input array.