The LeetCode 2762: Continuous Subarrays problem asks us to count the total number of subarrays where the absolute difference between any two elements is at most 2. Formally, for every pair of indices $i_1, i_2$ in the subarray, we must satisfy $|nums[i_1] - nums[i_2]| \le 2$. This condition is mathematically equivalent to checking if the difference between the maximum and minimum elements in the subarray is less than or equal to 2.

Brute Force Approach for Continuous Subarrays

The naive approach involves generating every possible subarray and checking the validity condition for each one.

1. Iterate through all possible starting positions i from 0 to n-1.
2. Iterate through all possible ending positions j from i to n-1.
3. For each subarray nums[i...j], scan its elements to find the minimum and maximum values.
4. If max_val - min_val <= 2, increment the counter.

python
# Pseudo-code for Brute Force
count = 0
for i in range(len(nums)):
    for j in range(i, len(nums)):
        sub = nums[i : j+1]
        if max(sub) - min(sub) <= 2:
            count += 1
return count

Time Complexity Analysis: This approach requires three nested loops (two for the boundaries, one implied for finding min/max). This results in a time complexity of $O(N^3)$. Even if we optimize the min/max finding to run incrementally, it remains $O(N^2)$. Given the constraint $N \le 10^5$, an $O(N^2)$ solution requires roughly $10^{10}$ operations, which will inevitably result in a Time Limit Exceeded (TLE) error.

Core Insight for Continuous Subarrays

The key intuition is that if a subarray ending at index R starting at index L (i.e., nums[L...R]) is valid, then every subarray ending at R contained within it (e.g., nums[L+1...R], nums[L+2...R]) is also valid.

Conversely, if adding a new element at R breaks the condition (making max - min > 2), we must shrink the window from the left (L) until the condition is restored. We do not need to reset R; we can simply slide L forward.

The fundamental invariant we must maintain is: $\max(\text{window}) - \min(\text{window}) \le 2$

To implement this efficiently, we need a data structure that allows us to:

1. Add an element.
2. Remove an element.
3. Retrieve the minimum and maximum values in the current window.

A Sorted Map (TreeMap in Java/C++) or a Hash Map (since the value range is very small) works perfectly here.

Visual Description: Imagine a window expanding to the right. As R moves to R+1, we include a new number. If this new number causes the difference between the largest and smallest numbers in our window to exceed 2, the window is "broken." We fix it by moving L to the right, ejecting numbers from the left side until the range of values in the window tightens back to $\le 2$. Once valid, the number of valid subarrays ending at R is simply the window's length, $R - L + 1$.

Execution Flow

Let's trace nums = [5, 4, 2, 4].

1. Start: L=0, R=0, Map={}.
2. R=0 (Val=5):
   • Add 5. Map={5:1}. Min=5, Max=5. Diff=0 (Valid).
   • Count += (0 - 0 + 1) = 1. Total=1.
3. R=1 (Val=4):
   • Add 4. Map={4:1, 5:1}. Min=4, Max=5. Diff=1 (Valid).
   • Count += (1 - 0 + 1) = 2. Total=3.
4. R=2 (Val=2):
   • Add 2. Map={2:1, 4:1, 5:1}. Min=2, Max=5. Diff=3 (Invalid).
   • Shrink: Remove nums[L] (5). L becomes 1. Map={2:1, 4:1}. Min=2, Max=4. Diff=2 (Valid).
   • Count += (2 - 1 + 1) = 2. Total=5.
5. R=3 (Val=4):
   • Add 4. Map={2:1, 4:2}. Min=2, Max=4. Diff=2 (Valid).
   • Count += (3 - 1 + 1) = 3. Total=8.

Final Output: 8.

Proof of Correctness

The algorithm relies on the property that if nums[L...R] is a continuous subarray, then nums[k...R] is also continuous for all $L < k \le R$. By finding the smallest $L$ such that nums[L...R] is valid (the widest possible window ending at $R$), we guarantee that we count all possible valid start points for the current end point $R$. The sliding window invariant ensures that we never count an invalid subarray and never miss a valid one because $L$ only moves forward when strictly necessary.

Reference Implementation

C++ Solution for LeetCode 2762

In C++, std::map is ordered, making begin() (min) and rbegin() (max) access efficient.

cpp
class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        long long count = 0;
        int left = 0;
        // Map stores value -> frequency
        // Ordered map keeps keys sorted, allowing O(1) access to min/max 
        // given the small constraint on range size.
        map<int, int> freq; 

        for (int right = 0; right < nums.size(); ++right) {
            freq[nums[right]]++;

            // While the condition is broken (max - min > 2)
            // freq.rbegin()->first accesses the largest key
            // freq.begin()->first accesses the smallest key
            while (freq.rbegin()->first - freq.begin()->first > 2) {
                freq[nums[left]]--;
                if (freq[nums[left]] == 0) {
                    freq.erase(nums[left]);
                }
                left++;
            }

            // Add the number of valid subarrays ending at 'right'
            count += (right - left + 1);
        }

        return count;
    }
};

Java Solution for LeetCode 2762

Java's TreeMap provides efficient access to the first (lowest) and last (highest) keys.

java
import java.util.TreeMap;

class Solution {
    public long continuousSubarrays(int[] nums) {
        long count = 0;
        int left = 0;
        // TreeMap keeps keys sorted naturally
        TreeMap<Integer, Integer> map = new TreeMap<>();

        for (int right = 0; right < nums.length; right++) {
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);

            // Check validity: max - min > 2
            while (map.lastKey() - map.firstKey() > 2) {
                map.put(nums[left], map.get(nums[left]) - 1);
                if (map.get(nums[left]) == 0) {
                    map.remove(nums[left]);
                }
                left++;
            }

            // All subarrays ending at 'right' starting from 'left' to 'right' are valid
            count += (right - left + 1);
        }

        return count;
    }
}

Python Solution for LeetCode 2762

In Python, we can use a standard dictionary. Since the window size (in terms of unique values) is constrained to be very small (max diff 2 means $\approx$ 3 keys), min() and max() on the dictionary keys are effectively $O(1)$.

python
from collections import defaultdict

class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        count = 0
        left = 0
        freq = defaultdict(int)
        
        for right, num in enumerate(nums):
            freq[num] += 1
            
            # Check condition. Since valid range is small, 
            # finding max/min of keys is effectively O(1).
            while max(freq) - min(freq) > 2:
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    del freq[nums[left]]
                left += 1
            
            # Add number of valid subarrays ending at current index
            count += (right - left + 1)
            
        return count

In all these cases, the logic add(right) -> while(invalid) remove(left) -> update_answer remains the same.