Given an integer array nums, return the number of subarrays of length 3 such that the sum of the first and third numbers equals exactly half of the second number.
Example 1:
Input: nums = [1,2,1,4,1]
Output: 1
Explanation:
Only the subarray [1,4,1] contains exactly 3 elements where the sum of the first and third numbers equals half the middle number.
Example 2:
Input: nums = [1,1,1]
Output: 0
Explanation:
[1,1,1] is the only subarray of length 3. However, its first and third numbers do not add to half the middle number.
Constraints:
3 <= nums.length <= 100-100 <= nums[i] <= 100Problem Overview: You are given an integer array and must count how many subarrays of length 3 satisfy a specific condition. For a subarray [a, b, c], the condition holds when the middle value equals the average of the first and third elements, which can be written as a + c = 2 * b.
Approach 1: Brute Force Enumeration (O(n) time, O(1) space)
The direct way is to examine every contiguous subarray of size three. Iterate from index 0 to n-3, extract the triple (nums[i], nums[i+1], nums[i+2]), and check whether nums[i] + nums[i+2] == 2 * nums[i+1]. Each check is constant time, and there are n-2 such subarrays, so the total time complexity is O(n) with O(1) extra space. This approach is conceptually brute force because it evaluates every possible length‑3 window independently without optimizing further.
Approach 2: Single Pass Sliding Window (O(n) time, O(1) space)
A cleaner implementation treats the problem as a fixed-size sliding window over the array. Move a window of length three across the array using a single loop. For each position i, interpret the window as (nums[i], nums[i+1], nums[i+2]) and check the arithmetic condition nums[i] + nums[i+2] == 2 * nums[i+1]. Because the window size never changes, there is no need for extra data structures—just index access and a simple arithmetic comparison. The traversal touches each element once, giving O(n) time and O(1) space.
This pattern appears frequently in sliding window problems with fixed window sizes. The key observation is the mathematical relationship between the three values. Rewriting the condition as a + c = 2b avoids floating-point averages and keeps the check constant time. The logic also mirrors properties of a three-element arithmetic progression, which connects the problem to simple math reasoning rather than heavier data structures.
Recommended for interviews: The single pass window is what interviewers expect. Start by explaining that only n-2 subarrays of size three exist, then iterate once and check the arithmetic condition. Mentioning the brute force enumeration shows you understand the search space, while implementing the single pass solution demonstrates clean reasoning and optimal O(n) time with constant space.
We traverse each subarray of length 3 in the array nums and check if twice the sum of the first and third numbers equals the second number. If it does, we increment the answer by 1.
After traversing, we return the answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n) | O(1) | Good for understanding the problem by explicitly checking every subarray of length three. |
| Single Pass Sliding Window | O(n) | O(1) | Best practical solution. Uses a fixed window over the array with minimal logic and constant memory. |
Count Subarrays of Length Three With a Condition | Easy | Leetcode 3392 | codestorywithMIK • codestorywithMIK • 3,266 views views
Watch 9 more video solutions →Practice Count Subarrays of Length Three With a Condition with our built-in code editor and test cases.
Practice on FleetCode