Count Subarrays of Length Three With a Condition — Easy Problem & Solution

Count the subarrays of length three where the sum of the first and third elements is exactly half of the second element.

Difficulty: Easy
Topics: Arrays, Sliding Window
Asked at: Amazon, Microsoft, Zoho
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Count the subarrays of length three where the sum of the first and third elements is exactly half of the second element.

Example 1

Input: nums = [1,2,1,4,1]
Output: 1
Explanation: [1,4,1]: 1 + 1 is half of 4.

Example 2

Input: nums = [1,1,1]
Output: 0
Explanation: 1 + 1 is not half of 1.

Example 3

Input: nums = [2,8,2,8,2]
Output: 2
Explanation: [2,8,2] appears twice.

Constraints

3 <= nums.length <= 100
-100 <= nums[i] <= 100

How to solve Count Subarrays of Length Three With a Condition

A fixed window of three with a constant-time test. The only subtlety is expressing 'half' without floating point or truncating division.

Approach

Slide i over every start with i + 3 <= n.
Test 2 · (nums[i] + nums[i+2]) == nums[i+1].
Count the triples that pass.

Why it works

a + c == b / 2 and 2(a + c) == b are equivalent over the integers, but the second form is exact: it needs no division, so an odd b simply fails rather than being silently rounded. Values stay small, so the doubling cannot overflow.

Complexity

Time — O(n)
Space — O(1)

Pitfalls

Writing nums[i] + nums[i+2] == nums[i+1] / 2 with integer division accepts odd nums[i+1] wrongly.
Using floating-point division invites rounding error for no benefit.
Negative values are allowed, so the condition can hold with a negative middle element.

Reference solution

Python

from typing import List

def countSubarrays(nums: List[int]) -> int:
    count = 0
    for i in range(len(nums) - 2):
        if 2 * (nums[i] + nums[i + 2]) == nums[i + 1]:
            count += 1
    return count

JavaScript

var countSubarrays = function(nums) {
    var count = 0;
    for (var i = 0; i + 3 <= nums.length; i++) {
        if (2 * (nums[i] + nums[i + 2]) === nums[i + 1]) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue