Count Subarrays of Length Three With a Condition
EasyPrompt
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] <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through all possible combinations of three indices (i, j, k) in the array and checks if they form a valid subarray of length 3 that satisfies the given condition.
Algorithm
- Initialize a counter
countto 0. - Iterate with an index
ifrom0tonums.length - 1. - Inside, iterate with an index
jfrom0tonums.length - 1. - Inside, iterate with an index
kfrom0tonums.length - 1. - If
j == i + 1andk == i + 2: - If
2 * (nums[i] + nums[k]) == nums[j]: - Increment
count. - Return
count.
Walkthrough
The core idea is to use three nested loops to pick three elements from the array at indices i, j, and k. Inside the innermost loop, we first validate if these indices actually form a contiguous subarray of length 3 by checking if j == i + 1 and k == i + 2. If they do, we then check if they satisfy the problem's condition. To avoid floating-point arithmetic, the condition nums[i] + nums[k] == nums[j] / 2 is rewritten as 2 * (nums[i] + nums[k]) == nums[j]. A counter is incremented for each valid subarray found.
class Solution { public int countSubarrays(int[] nums) { int n = nums.length; int count = 0; if (n < 3) { return 0; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { // Check if the indices form a contiguous subarray of length 3 if (j == i + 1 && k == i + 2) { // Check the condition // Using 2 * (a + c) == b to avoid floating point issues if (2 * (nums[i] + nums[k]) == nums[j]) { count++; } } } } } return count; }}Complexity
Time
O(n^3), where n is the length of the `nums` array. This is because of the three nested loops, each iterating up to `n` times.
Space
O(1), as we only use a constant amount of extra space for the counter and loop variables.
Trade-offs
Pros
Conceptually simple to understand, as it directly translates the problem of finding three elements into three loops.
Cons
Highly inefficient due to the cubic time complexity. It performs a lot of unnecessary checks for indices that do not form a contiguous subarray.
Not practical for larger input sizes, although it passes for the given constraints (n <= 100).
Solutions
Solution
class Solution {public int countSubarrays(int[] nums) { int ans = 0; for (int i = 1; i + 1 < nums.length; ++i) { if ((nums[i - 1] + nums[i + 1]) * 2 == nums[i]) { ++ans; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.