2762. Continuous Subarrays - Detailed Explanation

Problem Statement

Description:
Given an integer array nums, count the number of contiguous (continuous) subarrays such that the difference between the maximum and minimum elements in that subarray is less than or equal to 2.

A subarray is defined as a contiguous segment of the array. In other words, for any subarray nums[i...j], it must satisfy:

[ \text{max}(nums[i...j]) - \text{min}(nums[i...j]) \le 2 ]

Examples:

• Example 1:

  • Input: nums = [1, 2, 3]
  • Output: 6
  • Explanation:
    All possible subarrays are:
    • [1] → max = 1, min = 1, diff = 0
    • [2] → max = 2, min = 2, diff = 0
    • [3] → max = 3, min = 3, diff = 0
    • [1,2] → max = 2, min = 1, diff = 1
    • [2,3] → max = 3, min = 2, diff = 1
    • [1,2,3] → max = 3, min = 1, diff = 2
      All six subarrays satisfy the condition.

• Example 2:

  • Input: nums = [1, 3, 2]
  • Output: 6
  • Explanation:
    The subarrays are:
    • [1], [3], [2] (all valid)
    • [1,3] → diff = 2
    • [3,2] → diff = 1
    • [1,3,2] → max = 3, min = 1, diff = 2
      All six subarrays are valid.

Constraints:

• 1 \le \text{nums.length} \le 10^5 )
• The values in nums can be any integers.
• The condition to satisfy for a subarray is:
  (\text{max}(subarray) - \text{min}(subarray) \le 2)

Hints Before You Start

• Hint 1:
  When you extend a subarray by adding a new element (moving the right pointer), how can you quickly determine the new maximum and minimum in the current window?

• Hint 2:
  Since the array is processed sequentially, consider using a sliding window approach along with data structures (monotonic deques) that help you maintain the current window's maximum and minimum values in O(1) time.

• Hint 3:
  For every valid window ending at index right, every subarray that starts from any index between left and right is valid. Thus, you can add (right - left + 1) to your answer.

Approaches

Brute Force Approach

Idea:

• Check every possible subarray by using two nested loops.
• For each subarray, compute the maximum and minimum values and check whether their difference is ≤ 2.
• Drawbacks:
  This approach would run in O(n²) (or worse if you recompute max and min for each subarray) and is too slow for large arrays.

Optimal Approach – Sliding Window with Monotonic Deques

Idea:

• Use a sliding window approach to find all valid subarrays in one pass.
• Maintain two deques:
  • Max Deque: Keeps track of the maximum values in the current window (maintained in decreasing order).
  • Min Deque: Keeps track of the minimum values in the current window (maintained in increasing order).
• As you move the right pointer through the array:
  1. Update both deques to include the new element.
  2. While the difference between the front elements (the current maximum and minimum) is greater than 2, increment the left pointer and update the deques accordingly.
  3. For each index right, the number of valid subarrays ending at right is (right - left + 1).

Step-by-Step Overview:

1. Initialization:
   Set left = 0 and count = 0. Initialize two empty deques, one for maximum and one for minimum.

2. Iterate with Right Pointer:
   For each right from 0 to n-1:

   • Update Max Deque:
     Remove indices from the back while the current element is greater than the elements at those indices; then append right.

   • Update Min Deque:
     Remove indices from the back while the current element is smaller than the elements at those indices; then append right.

   • Shrink Window if Invalid:
     While the difference between nums[max_deque[0]] and nums[min_deque[0]] is greater than 2, move the left pointer:

     • If the left index is at the front of either deque, pop it.
     • Increment left.

   • Count Valid Subarrays:
     Add (right - left + 1) to the total count.

Complexity Analysis:

• Time Complexity: O(n) because each element is added and removed from the deques at most once.
• Space Complexity: O(n) in the worst-case scenario for the deques.

Code Implementations

Python Code (Sliding Window with Monotonic Deques)