2762. Continuous Subarrays

You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:

• Let i, i + 1, …, jbe 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.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [5,4,2,4]
Output: 8
Explanation:
Continuous subarray of size 1: [5], [4], [2], [4].
Continuous subarray of size 2: [5,4], [4,2], [2,4].
Continuous subarray of size 3: [4,2,4].
Thereare no subarrys of size 4.
Total continuous subarrays = 4 + 3 + 1 = 8.
It can be shown that there are no more continuous subarrays.

Example 2:

Input: nums = [1,2,3]
Output: 6
Explanation:
Continuous subarray of size 1: [1], [2], [3].
Continuous subarray of size 2: [1,2], [2,3].
Continuous subarray of size 3: [1,2,3].
Total continuous subarrays = 3 + 2 + 1 = 6.

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

Approach 01:

#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        int n = nums.size();
        long long result = 0; // Use long long for the result
        int left = 0; // Start of the current valid subarray

        deque<int> maxDeque; // Indices of potential maximum elements
        deque<int> minDeque; // Indices of potential minimum elements

        for (int right = 0; right < n; ++right) {
            // Maintain the maxDeque (decreasing order)
            while (!maxDeque.empty() && nums[maxDeque.back()] <= nums[right]) {
                maxDeque.pop_back();
            }
            maxDeque.push_back(right);

            // Maintain the minDeque (increasing order)
            while (!minDeque.empty() && nums[minDeque.back()] >= nums[right]) {
                minDeque.pop_back();
            }
            minDeque.push_back(right);

            // Check if the window is valid
            while (nums[maxDeque.front()] - nums[minDeque.front()] > 2) {
                // Shrink the window from the left
                if (maxDeque.front() == left) {
                    maxDeque.pop_front();
                }
                if (minDeque.front() == left) {
                    minDeque.pop_front();
                }
                ++left;
            }

            // Add the number of valid subarrays ending at `right`
            result += (long long)(right - left + 1); // Explicitly cast to long long
        }

        return result;
    }
};

from typing import List
from collections import deque

class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        result = 0
        left = 0  # Start of the current valid subarray

        max_deque = deque()  # Stores indices of potential maximum elements
        min_deque = deque()  # Stores indices of potential minimum elements

        for right in range(n):
            # Maintain the max deque (decreasing order)
            while max_deque and nums[max_deque[-1]] <= nums[right]:
                max_deque.pop()
            max_deque.append(right)

            # Maintain the min deque (increasing order)
            while min_deque and nums[min_deque[-1]] >= nums[right]:
                min_deque.pop()
            min_deque.append(right)

            # Check if the window is valid
            while nums[max_deque[0]] - nums[min_deque[0]] > 2:
                # Shrink the window from the left
                if max_deque[0] == left:
                    max_deque.popleft()
                if min_deque[0] == left:
                    min_deque.popleft()
                left += 1

            # Add the number of valid subarrays ending at `right`
            result += (right - left + 1)

        return result

Time Complexity

• Traversal:
  • The loop iterates through the array once, making this step \(O(n)\), where \(n\) is the size of the input array.
• Deque Operations:
  • Each element is added to and removed from the deques at most once during the traversal.
  • Since deque operations (push and pop) are \(O(1)\), maintaining the deques also takes \(O(n)\).
• Overall Time Complexity:

  The total time complexity is \(O(n)\), as all operations (traversal and deque maintenance) are linear.

Space Complexity

• Deques:
  • The maximum size of each deque is proportional to the size of the current sliding window.
  • In the worst case, each deque can hold \(O(n)\) elements, but typically, their size is much smaller due to the shrinking window.
  • Thus, the space used by both deques is \(O(n)\).
• Other Variables:
  • Variables like left, right, and result use \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(n)\), dominated by the space used for the deques.