# Continuous Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/continuous-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/continuous-subarrays
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Heap (Priority Queue), Ordered Set, Queue, Monotonic Queue
---
## Problem
You are given a **0-indexed** integer array `nums`. A subarray of `nums` is called **continuous** if:

* Let `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._

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].
There are 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`

# Approaches
## Brute Force Enumeration
This approach involves generating every possible subarray, and for each one, checking if it meets the 'continuous' criteria. The criteria is that the difference between the maximum and minimum element in the subarray must be less than or equal to 2.
**Time:** O(n^3). Three nested loops are used. The outer two loops select the subarray (`O(n^2)` pairs), and the inner loop finds the min/max in `O(n)` time. · **Space:** O(1). We only use a few variables to store the count, indices, min, and max.
**Pros:** Simple to conceptualize and implement.; Requires no extra data structures.
**Cons:** Extremely inefficient, with a cubic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
We use two nested loops to define the start (`i`) and end (`j`) indices of all possible subarrays. For each subarray `nums[i...j]`, we iterate through it a third time to find its minimum and maximum values. If `max - min <= 2`, we increment a counter. This method is simple to understand but highly inefficient due to the triple nested loops.

```java
public class Solution {
    public long continuousSubarrays(int[] nums) {
        long count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int minVal = Integer.MAX_VALUE;
                int maxVal = Integer.MIN_VALUE;
                // Find min and max in subarray nums[i..j]
                for (int k = i; k <= j; k++) {
                    minVal = Math.min(minVal, nums[k]);
                    maxVal = Math.max(maxVal, nums[k]);
                }
                if (maxVal - minVal <= 2) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate through each possible start index `i` from 0 to `n-1`.
- For each `i`, iterate through each possible end index `j` from `i` to `n-1`.
- For the subarray `nums[i...j]`, find the minimum (`minVal`) and maximum (`maxVal`) elements by iterating from `i` to `j`.
- If `maxVal - minVal <= 2`, increment `count`.
- After all subarrays are checked, return `count`.

## Optimized Brute Force
This approach improves upon the brute-force method by avoiding the third loop. As we extend a subarray from `nums[i...j]` to `nums[i...j+1]`, we can update the minimum and maximum values in constant time instead of re-scanning the entire subarray.
**Time:** O(n^2). Two nested loops are used. The operations inside the inner loop are O(1). · **Space:** O(1). Only a few variables are used for tracking state.
**Pros:** More efficient than the O(n^3) approach.; Still relatively easy to implement.
**Cons:** The quadratic time complexity is still too slow for the given constraints (`n <= 10^5`).
### Explanation
We iterate through all possible starting points `i` of a subarray. For each `i`, we start another loop for the endpoint `j`, from `i` to the end of the array. As we expand the subarray by incrementing `j`, we keep track of the minimum and maximum values seen so far within `nums[i...j]`. If `max - min <= 2`, we count this subarray. If the condition is violated, we know that any further extension of the subarray from `i` will also be invalid, so we can break the inner loop and move to the next starting point `i`.

```java
public class Solution {
    public long continuousSubarrays(int[] nums) {
        long count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int minVal = nums[i];
            int maxVal = nums[i];
            for (int j = i; j < n; j++) {
                minVal = Math.min(minVal, nums[j]);
                maxVal = Math.max(maxVal, nums[j]);
                if (maxVal - minVal <= 2) {
                    count++;
                } else {
                    // If nums[i..j] is not continuous,
                    // any subarray nums[i..k] where k > j won't be either.
                    break;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate through each possible start index `i` from 0 to `n-1`.
- For each `i`, initialize `minVal` and `maxVal` to `nums[i]`.
- Start an inner loop for the end index `j` from `i` to `n-1`.
- In the inner loop, update `minVal = min(minVal, nums[j])` and `maxVal = max(maxVal, nums[j])`.
- If `maxVal - minVal <= 2`, increment `count`.
- If `maxVal - minVal > 2`, break the inner loop, as any further extension will also be invalid.
- Return `count`.

## Sliding Window with Balanced Tree
This approach uses a sliding window and a balanced binary search tree (like Java's `TreeMap`) to maintain the elements within the current window. For each right endpoint of the window, we expand it and then shrink it from the left until the condition `max - min <= 2` is met. The number of valid subarrays ending at the current right endpoint can then be calculated easily.
**Time:** O(n log n). Each element is added to and removed from the `TreeMap` at most once. `TreeMap` operations take `O(log k)` time, where `k` is the window size. In the worst case, `k` can be up to `n`. · **Space:** O(n). In the worst case, the `TreeMap` might store all `n` elements if they are all distinct and form a valid window.
**Pros:** Significantly more efficient than O(n^2).; Passes the time limits for the given constraints.
**Cons:** Logarithmic factor in time complexity due to tree operations.; Higher space complexity compared to brute-force approaches.
### Explanation
We use a sliding window defined by `[left, right]`. We iterate `right` from 0 to `n-1`. For each `right`, we add `nums[right]` to a `TreeMap` which stores the elements in the window and their frequencies. The `TreeMap` allows us to find the min (`firstKey()`) and max (`lastKey()`) elements in the window in `O(log k)` time, where `k` is the number of distinct elements in the window. If `max - min > 2`, we shrink the window by incrementing `left` and removing `nums[left]` from the `TreeMap` until the condition is satisfied. Once the window `[left, right]` is valid, we know that all subarrays ending at `right` with a start index from `left` to `right` are also valid. There are `right - left + 1` such subarrays, which we add to our total count.

```java
import java.util.TreeMap;

public class Solution {
    public long continuousSubarrays(int[] nums) {
        long count = 0;
        int n = nums.length;
        TreeMap<Integer, Integer> windowCounts = new TreeMap<>();
        int left = 0;
        for (int right = 0; right < n; right++) {
            windowCounts.put(nums[right], windowCounts.getOrDefault(nums[right], 0) + 1);
            
            while (windowCounts.lastKey() - windowCounts.firstKey() > 2) {
                windowCounts.put(nums[left], windowCounts.get(nums[left]) - 1);
                if (windowCounts.get(nums[left]) == 0) {
                    windowCounts.remove(nums[left]);
                }
                left++;
            }
            
            count += (right - left + 1);
        }
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0`, `left = 0`, and a `TreeMap` to store element frequencies in the window.
- Iterate `right` from 0 to `n-1`.
- Add `nums[right]` to the `TreeMap`.
- While the difference between the max key and min key in the `TreeMap` is greater than 2:
  - Decrement the frequency of `nums[left]` in the `TreeMap`.
  - If the frequency becomes zero, remove the element from the `TreeMap`.
  - Increment `left`.
- Add `right - left + 1` to `count`.
- Return `count`.

## Sliding Window with Monotonic Deques
This is the most optimal approach, achieving linear time complexity. It uses a sliding window combined with two monotonic deques (double-ended queues). One deque maintains indices of elements in decreasing order of value to find the window's maximum in `O(1)` time. The other deque maintains indices in increasing order of value to find the window's minimum in `O(1)` time.
**Time:** O(n). Each element's index is added to and removed from each deque at most once. The `left` and `right` pointers traverse the array once. All operations are amortized O(1). · **Space:** O(n). In the worst case (e.g., a strictly increasing or decreasing array), the deques can store up to `n` indices.
**Pros:** Optimal time complexity.; Very efficient for large inputs.
**Cons:** The logic with two deques can be more complex to understand and implement correctly compared to other approaches.
### Explanation
We maintain a sliding window `[left, right]`. We also use two deques: `maxDeque` to track the maximum and `minDeque` to track the minimum. As we iterate `right` from 0 to `n-1`, we update the deques. For `maxDeque`, we remove indices from the end that correspond to values smaller than or equal to `nums[right]`, ensuring the values corresponding to indices are in decreasing order. For `minDeque`, we do the opposite to maintain increasing order. This way, `nums[maxDeque.peekFirst()]` is always the max and `nums[minDeque.peekFirst()]` is always the min of the current window. If `max - min > 2`, we shrink the window from the left by incrementing `left` and removing `left` from the deques if it's at the front. Once the window is valid, we add `right - left + 1` to our total count, representing all valid subarrays ending at `right`.

```java
import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public long continuousSubarrays(int[] nums) {
        long count = 0;
        int n = nums.length;
        Deque<Integer> maxDeque = new LinkedList<>();
        Deque<Integer> minDeque = new LinkedList<>();
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            // Maintain maxDeque (indices of decreasing values)
            while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] <= nums[right]) {
                maxDeque.pollLast();
            }
            maxDeque.addLast(right);
            
            // Maintain minDeque (indices of increasing values)
            while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= nums[right]) {
                minDeque.pollLast();
            }
            minDeque.addLast(right);
            
            // Shrink window if condition is violated
            while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > 2) {
                // If the leftmost element is the max/min, remove it from deque
                if (maxDeque.peekFirst() == left) {
                    maxDeque.pollFirst();
                }
                if (minDeque.peekFirst() == left) {
                    minDeque.pollFirst();
                }
                left++;
            }
            
            // Add count of valid subarrays ending at 'right'
            count += (right - left + 1);
        }
        
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0`, `left = 0`, and two deques, `maxDeque` and `minDeque`.
- Iterate `right` from 0 to `n-1`.
- Update `maxDeque`: remove indices from the tail that correspond to values less than or equal to `nums[right]`, then add `right`.
- Update `minDeque`: remove indices from the tail that correspond to values greater than or equal to `nums[right]`, then add `right`.
- While `nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > 2`:
  - If `maxDeque.peekFirst() == left`, remove it.
  - If `minDeque.peekFirst() == left`, remove it.
  - Increment `left`.
- Add `right - left + 1` to `count`.
- Return `count`.

# Solutions
### Java

```java
class Solution {
public
  long continuousSubarrays(int[] nums) {
    long ans = 0;
    int i = 0, n = nums.length;
    TreeMap<Integer, Integer> tm = new TreeMap<>();
    for (int j = 0; j < n; ++j) {
      tm.merge(nums[j], 1, Integer : : sum);
      while (tm.lastEntry().getKey() - tm.firstEntry().getKey() > 2) {
        tm.merge(nums[i], -1, Integer : : sum);
        if (tm.get(nums[i]) == 0) {
          tm.remove(nums[i]);
        }
        ++i;
      }
      ans += j - i + 1;
    }
    return ans;
  }
}

```

### Python

```python
from sortedcontainers import SortedList class Solution : def continuousSubarrays ( self , nums : List [ int ]) -> int : ans = i = 0 sl = SortedList () for x in nums : sl . add ( x ) while sl [ - 1 ] - sl [ 0 ] > 2 : sl . remove ( nums [ i ]) i += 1 ans += len ( sl ) return ans
```

### CPP

```cpp
class Solution {
public:
  long long continuousSubarrays(vector<int> &nums) {
    long long ans = 0;
    int i = 0, n = nums.size();
    multiset<int> s;
    for (int j = 0; j < n; ++j) {
      s.insert(nums[j]);
      while (*s.rbegin() - *s.begin() > 2) {
        s.erase(s.find(nums[i++]));
      }
      ans += j - i + 1;
    }
    return ans;
  }
};

```