LeetCode 2762: Continuous Subarrays

Problem Description

LeetCode Problem 2762

Given a 0-indexed integer array nums, we need to find the total number of continuous subarrays. A subarray is considered continuous if for any two indices i1, i2 in the subarray, the absolute difference between their values |nums[i1] - nums[i2]| is at most 2.

Solution Approach

The key insight is to use a sliding window technique with monotonic queues to efficiently track:

1. The maximum value in the current window
2. The minimum value in the current window

For a window to be valid, max - min ≤ 2 must hold true.

Why Monotonic Queues?

• We need to efficiently track both maximum and minimum values in a sliding window
• Monotonic queues give us O(1) access to max/min while maintaining the window

Solution

Here’s my Python solution using monotonic deques:

from collections import deque

class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        result = 0
        start = 0
        max_dq = deque()  # monotonic decreasing queue for maximum
        min_dq = deque()  # monotonic increasing queue for minimum
        
        for end in range(n):
            # Update max_dq
            while max_dq and nums[max_dq[-1]] < nums[end]:
                max_dq.pop()
            max_dq.append(end)
            
            # Update min_dq
            while min_dq and nums[min_dq[-1]] > nums[end]:
                min_dq.pop()
            min_dq.append(end)
            
            # Shrink window while it's not continuous
            while max_dq and min_dq and nums[max_dq[0]] - nums[min_dq[0]] > 2:
                start += 1
                while max_dq and max_dq[0] < start:
                    max_dq.popleft()
                while min_dq and min_dq[0] < start:
                    min_dq.popleft()
            
            # Add count of all valid subarrays ending at current position
            result += end - start + 1
        
        return result

Example Walkthrough

Let’s see how this works with the input [5,4,2,4]:

1. Starting with nums[0] = 5:

   • max_dq = [0], min_dq = [0]
   • Valid subarrays: [5]
   • result = 1

2. Adding nums[1] = 4:

   • max_dq = [0,1], min_dq = [1]
   • Valid subarrays: [4], [5,4]
   • result = 3

3. Adding nums[2] = 2:

   • max_dq = [0,1,2], min_dq = [2]
   • Window shrinks as 5-2 > 2
   • Valid subarrays: [2], [4,2]
   • result = 5

4. Adding nums[3] = 4:

   • max_dq = [1,3], min_dq = [2,3]
   • Valid subarrays: [4], [2,4], [4,2,4]
   • Final result = 8

Complexity Analysis

The solution has the following complexity characteristics:

• Time Complexity: $O(n)$

  • Each element is pushed and popped at most once from each deque
  • The start pointer only moves forward

• Space Complexity: $O(n)$

  • For storing the monotonic queues

Key Insights

1. Sliding Window Pattern:

   • For each ending position, find the leftmost valid starting position
   • Count all valid subarrays ending at current position

2. Monotonic Queue Benefits:

   • Maintains max/min values in O(1) time
   • Automatically removes elements that can’t be max/min
   • Stores indices to handle window boundaries

3. Window Validity:

   • A window is valid if max - min ≤ 2
   • Invalid windows are shrunk from the left

This pattern of using monotonic queues for sliding window problems is particularly useful when we need to track extremes (max/min) in a range efficiently.