We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Subarrays of Length Three With a Condition

Number: 3685

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given an integer array nums, return the number of contiguous subarrays of length 3 such that the sum of the first and third numbers equals exactly half of the middle number.

Key Insights

  • Iterate through the array considering every contiguous subarray of length 3.
  • For each subarray [a, b, c], check if b is even; if not, the condition cannot be met exactly.
  • If b is even, verify whether a + c equals b/2.
  • Use a simple loop to count the subarrays that satisfy the condition.

Space and Time Complexity

Time Complexity: O(n) - We make a single pass through the array. Space Complexity: O(1) - We use a few extra variables and no additional data structures.

Solution

We use a sliding window approach by iterating through the array from index 0 to n-3. For each index, we extract the triplet [nums[i], nums[i+1], nums[i+2]]. The middle element must be even because only then can half of it be an integer. If even, we compute half of the middle element and check if the sum of the first and third elements equals this value. Each valid subarray increments our counter. This method efficiently solves the problem in a single pass using constant space.

Code Solutions

# Python solution with line-by-line comments

def count_subarrays_with_condition(nums):
    # Initialize the count of valid subarrays to 0
    valid_count = 0
    # Loop through the array, stopping at len(nums) - 2
    for i in range(len(nums) - 2):
        a, b, c = nums[i], nums[i + 1], nums[i + 2]  # Extract the three elements
        # Check if the middle element is even
        if b % 2 == 0:
            half_b = b // 2  # Compute exactly half of b
            # Check if the sum of the first and third equals half of b
            if a + c == half_b:
                valid_count += 1  # Increment the counter if condition is met
    return valid_count

# Example usage:
# print(count_subarrays_with_condition([1,2,1,4,1]))  # Output: 1
← Back to All Questions