Watch 10 video solutions for Count Subarrays of Length Three With a Condition, a easy level problem involving Array. This walkthrough by codestorywithMIK has 3,266 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |