We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Continuous Subarrays

Number: 2868

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg, Amazon, Yahoo, Adobe

Problem Description

Given an array nums, count the total number of continuous subarrays for which the absolute difference between any two elements in the subarray is at most 2. A subarray is defined as a contiguous non-empty sequence within the array.

Key Insights

  • The condition on the subarray can be rephrased as ensuring that the difference between the maximum and minimum value in the subarray is at most 2.
  • A sliding window technique is ideal because subarrays are contiguous.
  • Use two monotonic queues (or deques) to efficiently track the minimum and maximum values in the current window.
  • When the condition breaks (i.e., max - min > 2), adjust the window by moving the left pointer appropriately.
  • The number of subarrays ending at the current right pointer is the window's length (right - left + 1).

Space and Time Complexity

Time Complexity: O(n) because each element is processed at most twice (once when added and once when removed). Space Complexity: O(n) in the worst case for the deques, though typical use is much lower.

Solution

We use a sliding window approach where we maintain two deques: one that keeps track of the maximum values (in decreasing order) and one for the minimum values (in increasing order) within the current window. For each new element at the right pointer, we update both deques. If the difference between the front elements of the maximum and minimum deques exceeds 2, we slide the left pointer until the condition is restored. The count of valid subarrays ending at the current right index is the size of the window, which is then added to the overall answer.

Code Solutions

from collections import deque

def continuousSubarrays(nums):
    # Deques for storing indices for minimum and maximum values
    min_deque = deque()
    max_deque = deque()
    left = 0
    count = 0
    
    # Iterate over each element as the right end of the window
    for right, num in enumerate(nums):
        # Maintain min_deque: remove elements greater than current num
        while min_deque and nums[min_deque[-1]] > num:
            min_deque.pop()
        min_deque.append(right)
        
        # Maintain max_deque: remove elements smaller than current num
        while max_deque and nums[max_deque[-1]] < num:
            max_deque.pop()
        max_deque.append(right)
        
        # If current window doesn't satisfy condition, slide left pointer
        while nums[max_deque[0]] - nums[min_deque[0]] > 2:
            # Move left pointer and remove if it is out of window
            if min_deque[0] == left:
                min_deque.popleft()
            if max_deque[0] == left:
                max_deque.popleft()
            left += 1
        
        # Count all subarrays ending at right index
        count += (right - left + 1)
    
    return count

# Example usage:
nums = [5,4,2,4]
print(continuousSubarrays(nums))  # Expected output: 8
← Back to All Questions