
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:
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.
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.
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.
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.
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
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
andend
denote the boundaries of the current sliding window. smallest
andlargest
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
andend
at the beginning of the array, and variables for storing the current minimum and maximum of the elements within the window defined bystart
andend
. - 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
andend-1
using the formula for the sum of the first N natural numbers. Add this tosum
and resetstart
to the currentend
, also resetting the minimum and maximum to the current element atend
. - Subsequently, adjust
start
backwards while the difference between the element atend
andstart-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
andend
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 ofend
, 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
, wherecurrent_length
is the length of the window. - Reset the
start
pointer to the current position ofend
to start a new window. Adjust thestart
pointer if necessary to include any earlier values that do not violate the maximum-minimum condition when combined with the currentend
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.
No comments yet.