Continuous Subarrays

Updated on 08 May, 2025
Continuous Subarrays header image

Problem Statement

In this problem, you are provided with a 0-indexed integer array nums. You need to count the subarrays that are labeled as continuous based on a specific criterion. A subarray is considered continuous if the absolute difference between any two of its elements does not exceed 2. Specifically, for any indices (i1) and (i2) that lie between the indices defining the subarray (i) and (j), the condition (0 \leq |nums[i1] - nums[i2]| \leq 2) should hold true. You are tasked with identifying and returning the total number of such continuous subarrays. Each subarray forms a contiguous, non-empty sequence extracted from the original array.

Examples

Example 1

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 and Intuition

Understanding the requirement that all elements in a continuous subarray should have differences of no greater than 2 from each other, certain observations can help in forming an optimal approach:

  1. Single Element Subarrays: Every individual element in the array forms a continuous subarray by default since there are no other elements to compare differences with.

  2. Multi-element Subarrays: When adding a new element to a potential continuous subarray, ensure that this new element maintains the continuous condition with all previously added elements. If it doesn't, a new subarray must start from this element or some point after.

  3. Two-Pointer Technique: This problem lends itself well to a sliding window or two-pointer approach. A typical strategy would be:

    • Start with two pointers at the beginning of the array.
    • Expand the "end" pointer to include more elements into the current window as long as they comply with the continuous subarray condition.
    • If adding a new element breaks the condition, move the "start" pointer to reduce the window size until the condition is fulfilled again or reset it based on the last valid subarray.
  4. Counting Subarrays: Every time you expand the window by moving the "end" pointer and the conditions are satisfied, all subarrays ending at the "end" and starting from "start" up to "end" are valid. The number of these subarrays is given by the length of the window.

  5. Avoiding Overlap: Ensure that while you adjust the "start" pointer, you're taking into account previously considered elements so subarrays are not counted multiple times.

By methodically expanding and contracting the window based on the condition imposed by the problem and counting eligible subarrays, you can ensure you capture all continuous subarrays as defined.

Solutions

  • C++
  • Java
  • Python
cpp
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.

java
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.

python
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.

Comments

No comments yet.