LeetCode 3392 - Count Subarrays of Length Three With a Condition
The problem gives us an integer array nums and asks us to count how many contiguous subarrays of length exactly 3 satisfy a specific mathematical condition.
Difficulty: 🟢 Easy
Topics: Array
Solution
Problem Understanding
The problem gives us an integer array nums and asks us to count how many contiguous subarrays of length exactly 3 satisfy a specific mathematical condition.
For every subarray of length 3, we look at:
- the first element
- the second element
- the third element
If:
$$\text{first} + \text{third} = \frac{\text{second}}{2}$$
then that subarray contributes 1 to the answer.
Another equivalent way to write the condition is:
$$2 \times (\text{first} + \text{third}) = \text{second}$$
This transformed version is usually easier to implement because it avoids dealing with fractions or floating point arithmetic.
The input array length is between 3 and 100, so the array is very small. The values themselves are also small, ranging from -100 to 100. These constraints tell us that performance is not a major concern, and even a straightforward solution will easily fit within time limits.
The important detail is that we only consider contiguous subarrays of exactly length 3. We are not checking all subsequences or all possible lengths.
Several edge cases are worth noting:
- Arrays with exactly
3elements contain only one candidate subarray. - Negative numbers can appear, so the condition must work correctly for negatives as well.
- The middle value may be odd. In that case, half of it is not an integer, which means the condition cannot hold for integer first and third values. Using the transformed equation avoids issues here naturally.
- Multiple overlapping valid subarrays may exist.
Approaches
Brute Force Approach
The most direct solution is to generate every possible subarray of length 3, then check whether it satisfies the required condition.
For each starting index i, we examine:
nums[i]nums[i + 1]nums[i + 2]
We then verify whether:
$$nums[i] + nums[i+2] = \frac{nums[i+1]}{2}$$
If the condition is true, we increment the answer.
This approach is correct because every valid subarray must have exactly length 3, and we examine all such subarrays exactly once.
A truly brute force implementation might explicitly construct temporary subarrays using slicing. That introduces unnecessary extra work and memory allocation.
Optimal Approach
The key observation is that every valid subarray has fixed size 3. Because of this, we never need nested loops, additional data structures, or sliding window bookkeeping.
We can simply iterate once through the array and directly inspect each consecutive triple.
Another useful observation is that comparing against half of the middle element may involve fractions. Instead of using division, we rewrite the condition as:
$$2 \times (nums[i] + nums[i+2]) = nums[i+1]$$
This avoids floating point arithmetic entirely and keeps the implementation clean and precise.
Since each triple is processed once, the solution runs in linear time.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(1) or O(3) | Checks every length-3 subarray directly |
| Optimal | O(n) | O(1) | Single pass using arithmetic transformation |
Algorithm Walkthrough
- Initialize a variable
countto0.
This variable stores how many valid subarrays we have found so far.
2. Iterate through the array from index 0 to len(nums) - 3.
We stop at len(nums) - 3 because each subarray requires three elements:
- current element
- next element
- element after that
- For each index
i, identify the three elements:
- first =
nums[i] - middle =
nums[i + 1] - third =
nums[i + 2]
- Check the transformed condition:
$$2 \times (first + third) = middle$$
This avoids division and guarantees exact integer arithmetic.
5. If the condition is true, increment count.
This means the current length-3 subarray satisfies the requirement.
6. After processing all possible triples, return count.
Why it works
The algorithm works because every contiguous subarray of length 3 appears exactly once during the iteration. For each such subarray, we directly verify the mathematical condition required by the problem. Since no candidate is skipped and no candidate is counted multiple times, the final count is correct.
Python Solution
from typing import List
class Solution:
def countSubarrays(self, nums: List[int]) -> int:
count = 0
for i in range(len(nums) - 2):
first = nums[i]
middle = nums[i + 1]
third = nums[i + 2]
if 2 * (first + third) == middle:
count += 1
return count
The implementation begins by initializing a counter variable named count.
The loop runs from 0 through len(nums) - 3, ensuring that every iteration has access to three consecutive elements.
Inside the loop, the three values are extracted into clearly named variables: first, middle, and third. This improves readability and makes the condition easier to understand.
The condition:
2 * (first + third) == middle
is the integer-safe version of the original requirement. If the condition holds, the algorithm increments the counter.
Finally, the function returns the total number of valid subarrays.
Go Solution
func countSubarrays(nums []int) int {
count := 0
for i := 0; i < len(nums)-2; i++ {
first := nums[i]
middle := nums[i+1]
third := nums[i+2]
if 2*(first+third) == middle {
count++
}
}
return count
}
The Go implementation follows the same logic as the Python version.
Slices in Go already provide efficient indexed access, so no additional data structures are required. Integer arithmetic is used throughout, which avoids floating point precision concerns.
There is no special handling needed for empty arrays because the problem guarantees the array length is at least 3.
Worked Examples
Example 1
Input:
nums = [1, 2, 1, 4, 1]
We examine every contiguous subarray of length 3.
| Index | Subarray | Calculation | Valid? | Count |
|---|---|---|---|---|
| 0 | [1, 2, 1] | 2 × (1 + 1) = 4, middle = 2 | No | 0 |
| 1 | [2, 1, 4] | 2 × (2 + 4) = 12, middle = 1 | No | 0 |
| 2 | [1, 4, 1] | 2 × (1 + 1) = 4, middle = 4 | Yes | 1 |
Final answer:
1
Example 2
Input:
nums = [1, 1, 1]
There is only one subarray of length 3.
| Index | Subarray | Calculation | Valid? | Count |
|---|---|---|---|---|
| 0 | [1, 1, 1] | 2 × (1 + 1) = 4, middle = 1 | No | 0 |
Final answer:
0
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each length-3 subarray is checked once |
| Space | O(1) | Only a few variables are used |
The algorithm performs a single pass across the array. Since each iteration does constant work, the runtime grows linearly with the input size.
No additional arrays, hash maps, or auxiliary data structures are created, so the space usage remains constant.
Test Cases
from typing import List
class Solution:
def countSubarrays(self, 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
solution = Solution()
assert solution.countSubarrays([1, 2, 1, 4, 1]) == 1 # provided example with one valid subarray
assert solution.countSubarrays([1, 1, 1]) == 0 # provided example with no valid subarray
assert solution.countSubarrays([1, 4, 1]) == 1 # minimum length array, valid
assert solution.countSubarrays([0, 0, 0]) == 1 # zeros satisfy the condition
assert solution.countSubarrays([-1, -4, -1]) == 1 # negative numbers
assert solution.countSubarrays([2, 8, 2, 8, 2]) == 3 # overlapping valid subarrays
assert solution.countSubarrays([1, 3, 1]) == 0 # middle element is odd
assert solution.countSubarrays([5, 20, 5, 1, 2, 1]) == 2 # multiple separated valid subarrays
assert solution.countSubarrays([100, -200, 100]) == 1 # extreme values within constraints
assert solution.countSubarrays([1, 2, 3, 4, 5]) == 0 # no valid subarrays
| Test | Why |
|---|---|
[1, 2, 1, 4, 1] |
Verifies the first official example |
[1, 1, 1] |
Verifies the second official example |
[1, 4, 1] |
Tests minimum valid input size |
[0, 0, 0] |
Ensures zero values work correctly |
[-1, -4, -1] |
Confirms negative numbers are handled properly |
[2, 8, 2, 8, 2] |
Tests overlapping valid subarrays |
[1, 3, 1] |
Checks odd middle values |
[5, 20, 5, 1, 2, 1] |
Tests multiple independent matches |
[100, -200, 100] |
Verifies behavior near constraint boundaries |
[1, 2, 3, 4, 5] |
Confirms correct handling when no matches exist |
Edge Cases
One important edge case is an array with exactly three elements. In this situation, there is only one possible subarray to evaluate. Off by one errors are common here because an incorrect loop boundary could skip the only valid triple. The implementation handles this correctly by iterating up to len(nums) - 2.
Another important edge case involves negative numbers. Since the problem allows values as small as -100, the arithmetic condition must work correctly for negatives. The implementation uses integer arithmetic only, so expressions such as:
$$2 \times (-1 + -1) = -4$$
are evaluated correctly without any special handling.
A third edge case occurs when the middle value is odd. Since half of an odd integer is not an integer, the condition cannot be satisfied by integer first and third values. Using the transformed equation:
$$2 \times (first + third) = middle$$
naturally handles this case because the left side is always even. Odd middle values automatically fail the comparison.
Another subtle edge case is overlapping valid subarrays. For example:
[2, 8, 2, 8, 2]
contains three valid triples that overlap heavily. The algorithm processes every starting index independently, so overlapping subarrays are counted correctly without interference.