Continuous Subarrays

LeetCode 2762: Continuous Subarrays Solution & Explanation

Problem Overview

TL;DR: Use a sliding window to maintain a range of indices $[L, R]$ where the difference between the maximum and minimum values in the window never exceeds 2, adding $R - L + 1$ to the total count at each step.

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.

1# Pseudo-code for Brute Force
2count = 0
3for i in range(len(nums)):
4    for j in range(i, len(nums)):
5        sub = nums[i : j+1]
6        if max(sub) - min(sub) <= 2:
7            count += 1
8return 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.

Algorithm Strategy: Sliding Window Patterns

1. Initialize Pointers: Set left and right to 0. Initialize a variable count to 0.
2. State Management: Use a frequency map (or Ordered Map) to track the count of each number currently in the window. This allows us to determine min and max efficiently.
3. Expand Window: Iterate right from 0 to nums.length - 1. Add nums[right] to the map.
4. Shrink Window (Enforce Constraint): Check if the difference between the largest key and smallest key in the map is $> 2$.
   • While the condition is violated, decrement the count of nums[left] in the map.
   • If the count of nums[left] drops to 0, remove the key entirely to update the min/max correctly.
   • Increment left.
5. Accumulate Answer: Once the window is valid, add right - left + 1 to count. This mathematical trick works because every valid window $[L, R]$ introduces exactly $R - L + 1$ new valid subarrays ending at index $R$.

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.

Pattern Reuse Notes

The Sliding Window - Variable Size pattern is versatile. Understanding how to expand right and shrink left based on a condition applies directly to these problems:

• LeetCode 3: Longest Substring Without Repeating Characters (Condition: No duplicate characters)
• LeetCode 76: Minimum Window Substring (Condition: Window contains all required characters)
• LeetCode 209: Minimum Size Subarray Sum (Condition: Sum $\ge$ target)
• LeetCode 219: Contains Duplicate II (Condition: Window size $\le k$)

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

Reference Implementation

C++ Solution for LeetCode 2762

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

1class Solution {
2public:
3    long long continuousSubarrays(vector<int>& nums) {
4        long long count = 0;
5        int left = 0;
6        // Map stores value -> frequency
7        // Ordered map keeps keys sorted, allowing O(1) access to min/max 
8        // given the small constraint on range size.
9        map<int, int> freq; 
10
11        for (int right = 0; right < nums.size(); ++right) {
12            freq[nums[right]]++;
13
14            // While the condition is broken (max - min > 2)
15            // freq.rbegin()->first accesses the largest key
16            // freq.begin()->first accesses the smallest key
17            while (freq.rbegin()->first - freq.begin()->first > 2) {
18                freq[nums[left]]--;
19                if (freq[nums[left]] == 0) {
20                    freq.erase(nums[left]);
21                }
22                left++;
23            }
24
25            // Add the number of valid subarrays ending at 'right'
26            count += (right - left + 1);
27        }
28
29        return count;
30    }
31};

Java Solution for LeetCode 2762

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

1import java.util.TreeMap;
2
3class Solution {
4    public long continuousSubarrays(int[] nums) {
5        long count = 0;
6        int left = 0;
7        // TreeMap keeps keys sorted naturally
8        TreeMap<Integer, Integer> map = new TreeMap<>();
9
10        for (int right = 0; right < nums.length; right++) {
11            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
12
13            // Check validity: max - min > 2
14            while (map.lastKey() - map.firstKey() > 2) {
15                map.put(nums[left], map.get(nums[left]) - 1);
16                if (map.get(nums[left]) == 0) {
17                    map.remove(nums[left]);
18                }
19                left++;
20            }
21
22            // All subarrays ending at 'right' starting from 'left' to 'right' are valid
23            count += (right - left + 1);
24        }
25
26        return count;
27    }
28}

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)$.

1from collections import defaultdict
2
3class Solution:
4    def continuousSubarrays(self, nums: List[int]) -> int:
5        count = 0
6        left = 0
7        freq = defaultdict(int)
8        
9        for right, num in enumerate(nums):
10            freq[num] += 1
11            
12            # Check condition. Since valid range is small, 
13            # finding max/min of keys is effectively O(1).
14            while max(freq) - min(freq) > 2:
15                freq[nums[left]] -= 1
16                if freq[nums[left]] == 0:
17                    del freq[nums[left]]
18                left += 1
19            
20            # Add number of valid subarrays ending at current index
21            count += (right - left + 1)
22            
23        return count