Continuous Subarrays

class Solution {
public:
    long long countSubarrays(vector<int>& data) {
        int start = 0, end = 0;
        int smallest, largest;
        long long length = 0, tally = 0;
    
        smallest = largest = data[start];
        for (end = 0; end < data.size(); end++) {
            smallest = min(smallest, data[end]);
            largest = max(largest, data[end]);
    
            if (largest - smallest > 2) {
                length = end - start;
                tally += (length * (length + 1) / 2);
    
                start = end;
                smallest = largest = data[end];
    
                while (start > 0 && abs(data[end] - data[start - 1]) <= 2) {
                    start--;
                    smallest = min(smallest, data[start]);
                    largest = max(largest, data[start]);
                }
    
                if (start < end) {
                    length = end - start;
                    tally -= (length * (length + 1) / 2);
                }
            }
        }
    
        length = end - start;
        tally += (length * (length + 1) / 2);
    
        return tally;
    }
};

This C++ program defines a function to calculate the total number of continuous subarrays where the difference between the smallest and largest element does not exceed 2. The function employs a sliding window technique to efficiently iterate through the input vector, tracking the start and end points of potential subarrays.

• A countSubarrays function accepts a vector of integers.
• Variables start and end denote the boundaries of the current sliding window.
• smallest and largest track the minimum and maximum values within the window.
• length calculates the size of the current valid subarray.
• tally accumulates the count of qualifying subarrays.

The key logic revolves around expanding the window by increasing end and adjusting start when the condition largest - smallest > 2 is met. This involves resetting the window at the new position and potentially backtracking to include earlier elements if they meet the required condition. This ensures all possible subarrays are counted, adding their count using the formula for the sum of the first n natural numbers (n * (n + 1) / 2), and subtracting counts appropriately when the window adjusts backwards.

The function then returns the total count of such subarrays, calculated in tally. Be aware of the nuances of the sliding window adjustment, especially the backtracking part, to fully understand the solution's efficiency and correctness.

class Solution {
    public long sumSubarrays(int[] arr) {
        int start = 0, end = 0;
        int minimum, maximum;
        long count = 0, sum = 0;
    
        minimum = maximum = arr[end];
    
        for (end = 0; end < arr.length; end++) {
            minimum = Math.min(minimum, arr[end]);
            maximum = Math.max(maximum, arr[end]);
    
            if (maximum - minimum > 2) {
                count = end - start;
                sum += ((count * (count + 1)) / 2);
    
                start = end;
                minimum = maximum = arr[end];
    
                while (start > 0 && Math.abs(arr[end] - arr[start - 1]) <= 2) {
                    start--;
                    minimum = Math.min(minimum, arr[start]);
                    maximum = Math.max(maximum, arr[start]);
                }
    
                if (start < end) {
                    count = end - start;
                    sum -= ((count * (count + 1)) / 2);
                }
            }
        }
    
        count = end - start;
        sum += ((count * (count + 1)) / 2);
    
        return sum;
    }
}

The provided Java code defines a method sumSubarrays in a class named Solution, which computes the sum of sizes of continuous subarrays where the difference between the minimum and maximum elements does not exceed 2. Here is a summary of how the code achieves this:

• Initialize pointers start and end at the beginning of the array, and variables for storing the current minimum and maximum of the elements within the window defined by start and end.
• Utilize a for-loop to traverse elements in the array using end as the loop variable.
• Within the loop, update the current minimum and maximum values, and check if their difference exceeds 2.
• If true, calculate the number of subarrays that can be formed between start and end-1 using the formula for the sum of the first N natural numbers. Add this to sum and reset start to the current end, also resetting the minimum and maximum to the current element at end.
• Subsequently, adjust start backwards while the difference between the element at end and start-1 remains within the constraint. Adjust the sum to remove over-counted subarrays due to the backward adjustment.
• After the loop, add the subarray count from the last valid segment [start, end-1].
• Finally, return sum which contains the overall sum of all valid subarray sizes.

This solution leverages the window sliding technique combined with a check and adjustment strategy to effectively account for all subarrays meeting the condition without exceeding O(n) complexity.

class Solution:
    def findContinuousSubarrays(self, numbers: List[int]) -> int:
        end = start = 0
        current_length = count = 0
            
        # Set initial minimum and maximum with first element
        minimum = maximum = numbers[end]
    
        for end in range(len(numbers)):
            # Adjust current minimum and maximum
            minimum = min(minimum, numbers[end])
            maximum = max(maximum, numbers[end])
    
            # Check if the window violates the condition (difference greater than 2)
            if maximum - minimum > 2:
                # Calculate subarrays for previous valid segment
                current_length = end - start
                count += current_length * (current_length + 1) // 2
    
                # Establish new window starting at the current index
                start = end
                minimum = maximum = numbers[end]
    
                # Adjust the start position
                while start > 0 and abs(numbers[end] - numbers[start - 1]) <= 2:
                    start -= 1
                    minimum = min(minimum, numbers[start])
                    maximum = max(maximum, numbers[start])
    
                # Correct the overcounted subarrays if there was an expansion
                if start < end:
                    current_length = end - start
                    count -= current_length * (current_length + 1) // 2
    
        # Calculate subarrays for the last valid window
        current_length = end - start + 1
        count += current_length * (current_length + 1) // 2
    
        return count

The solution implements a method to count all continuous subarrays within an array where the absolute difference between the maximum and minimum values does not exceed 2. The approach uses a sliding window technique to efficiently process the array without needing to check every possible subarray explicitly. Here's how the solution works:

• Initialize two pointers start and end at the beginning of the array. These pointers help define the current window of numbers being considered.
• Track the current window's minimum and maximum values dynamically as the end pointer moves through the array.
• Move the end pointer across the array. For each new position of end, update the minimum and maximum for the window.
• If the difference between the current window's maximum and minimum exceeds 2, calculate the number of valid subarrays within this window before the condition was violated using the formula current_length * (current_length + 1) // 2, where current_length is the length of the window.
• Reset the start pointer to the current position of end to start a new window. Adjust the start pointer if necessary to include any earlier values that do not violate the maximum-minimum condition when combined with the current end value.
• Finally, account for the last window after the main loop completes since it might not have been processed within the loop.

The final result, stored in count, is returned, representing the total number of valid subarrays found within the given array. This method ensures an optimal solution avoiding a brute force approach, thus reducing time complexity dramatically compared to simpler, less efficient methods.