Count Subarrays of Length Three With a Condition

Difficulty: Easy | Acceptance: 61.40% | Paid: No Topics: Array

Given a 0-indexed integer array nums, return the number of subarrays of length 3 where the middle element is strictly greater than the other two elements.

Formally, count the number of indices i such that:

• 0 < i < nums.length - 1
• nums[i] > nums[i - 1]
• nums[i] > nums[i + 1]

Table of Contents

• Examples
• Constraints
• Linear Scan
• Sliding Window
• Functional Approach

Examples

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
1 <= nums[i] <= 100

Linear Scan

Intuition We iterate through the array and check every element that could be the middle of a subarray of length 3. This corresponds to indices 1 through n-2.

Steps

• Initialize a counter to 0.
• Iterate through the array starting from index 1 to the second to last index (length - 2).
• For each index i, check if nums[i] is strictly greater than nums[i-1] and nums[i+1].
• If the condition is met, increment the counter.
• Return the counter.

class Solution:
    def countSubarrays(self, nums: List[int]) -> int:
        count = 0
        n = len(nums)
        for i in range(1, n - 1):
            if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
                count += 1
        return count

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Most efficient approach for this problem.

Sliding Window

Intuition We can visualize a window of size 3 sliding across the array. At each step, we check the middle element of the current window.

Steps

• Initialize a counter to 0.
• Iterate from index 0 to n - 3 (inclusive).
• For each starting index i, the window covers indices i, i+1, i+2.
• Check if nums[i+1] (the middle) is greater than nums[i] and nums[i+2].
• Increment counter if true.
• Return the counter.

class Solution:
    def countSubarrays(self, nums: List[int]) -> int:
        count = 0
        n = len(nums)
        for i in range(n - 2):
            if nums[i + 1] > nums[i] and nums[i + 1] > nums[i + 2]:
                count += 1
        return count

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Conceptually similar to Linear Scan, but focuses on the window boundaries.

Functional Approach

Intuition We use functional programming constructs like filter, reduce, or stream operations to count the valid indices without explicit loop management.

Steps

• Generate a range of valid middle indices (1 to n-2).
• Filter this range based on the peak condition.
• Count the number of remaining indices.

class Solution:
    def countSubarrays(self, nums: List[int]) -> int:
        return sum(1 for i in range(1, len(nums) - 1) if nums[i] > nums[i - 1] and nums[i] > nums[i + 1])

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Concise syntax, often preferred in modern codebases for simple logic.