Leetcode 3392. Count Subarrays of Length Three With a Condition

Let's understand what we're being asked to do. We have an array like [2, 4, 1, 3, 5] and need to count how many contiguous subarrays of length 3 satisfy a specific arithmetic condition.

For each window of 3 consecutive elements [a, b, c], we check: does a + c equal exactly half of b? In other words, is a + c = b / 2?

Let's trace through the example [2, 4, 1, 3, 5]:

• Window [2, 4, 1]: Check if 2 + 1 = 4 / 2 → 3 = 2? No.
• Window [4, 1, 3]: Check if 4 + 3 = 1 / 2 → 7 = 0.5? No.
• Window [1, 3, 5]: Check if 1 + 5 = 3 / 2 → 6 = 1.5? No.

So the count is 0 for this example.

Important constraint: We're looking at every possible contiguous subarray of length 3, sliding through the array one position at a time.

Edge cases to consider: What if the array has fewer than 3 elements? (return 0). What if the middle element is odd (so b / 2 is not an integer)? What if the sum a + c is negative?

We need to examine every consecutive triplet in the array. For an array of length n, there are exactly n - 2 such triplets (starting at indices 0, 1, 2, ..., n-3).

For each triplet [nums[i], nums[i+1], nums[i+2]], we simply check the arithmetic condition: nums[i] + nums[i+2] == nums[i+1] / 2.

This is a sliding window of fixed size 3. We don't need to track complex state or remember previous windows - each window is independent.

The key insight is that we can check each window in constant time O(1), and we have O(n) windows to check, giving us linear time overall.

Imagine sliding a frame of width 3 across the array, one position at a time:

[2, 4, 1, 3, 5]
 [---]           Check: 2 + 1 vs 4/2
    [---]        Check: 4 + 3 vs 1/2
       [---]     Check: 1 + 5 vs 3/2

At each position, we perform a simple arithmetic check. Count how many positions satisfy the condition. This is the essence of the fixed-size sliding window pattern.

Use a fixed-size sliding window of length 3 to iterate through the array. For each window starting at index i, extract the three elements [nums[i], nums[i+1], nums[i+2]] and check if nums[i] + nums[i+2] equals exactly nums[i+1] / 2. Increment a counter each time the condition is satisfied. This approach processes each element at most once as the window slides, achieving linear time complexity.

def count_valid_subarrays(nums):
    """
    Count contiguous subarrays of length 3 where first + third = middle / 2.
    Uses sliding window approach for O(n) time complexity.
    """
    # Initialize counter for valid subarrays
    count = 0
    
    # Slide window of size 3 through array
    for i in range(len(nums) - 2):
        # Extract three elements in current window
        first = nums[i]
        middle = nums[i + 1]
        third = nums[i + 2]
        
        # Check if first + third equals exactly middle / 2
        if first + third == middle / 2:
            count += 1
    
    return count

• Fixed-size sliding window pattern: When a problem asks about contiguous subarrays of fixed length (here, length 3), use a sliding window that moves one element at a time - this transforms an O(n*k) nested loop approach into O(n) by reusing overlapping elements between consecutive windows.
• Direct arithmetic validation: For simple element relationship checks within small windows, directly access elements by index (arr[i], arr[i+1], arr[i+2]) rather than maintaining complex window state - this keeps code readable and avoids unnecessary data structure overhead.
• Boundary-aware iteration: When sliding a window of size k, iterate only until index n-k (or i+k-1 < n) to prevent index-out-of-bounds errors - the last valid window starts at position n-k, not n-1, which is a common off-by-one mistake.
• Floating-point precision handling: When checking if arr[i] + arr[i+2] equals arr[i+1]/2, be cautious with division - either multiply both sides (2*(arr[i] + arr[i+2]) == arr[i+1]) to avoid floating-point errors, or use appropriate epsilon comparison for decimal values.
• Counter accumulation pattern: For problems counting subarrays that satisfy conditions, use a simple counter variable incremented when conditions are met - this is more efficient than storing qualifying subarrays in a list when only the count is needed.
• Window size generalization: This technique extends to any fixed-window constraint problem (k-element sums, products, averages, or custom predicates) - recognize that fixed-size windows with element-wise operations are ideal candidates for O(n) linear scans.