LeetCode 3874 - Valid Subarrays With Exactly One Peak

Difficulty: 🟡 Medium
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to count the number of contiguous subarrays of a given integer array nums that contain exactly one peak, where a peak is defined as an element nums[i] that is strictly greater than both its immediate neighbors nums[i-1] and nums[i+1]. Furthermore, for a subarray to be valid, the distance from the peak to the left end of the subarray must be at most k, and the distance from the peak to the right end must also be at most k.

The input nums is a list of integers of length n (up to 10^5), and k is an integer between 1 and n. The output is a single integer representing the total number of valid subarrays.

Important points from the constraints:

The array can be quite large (n up to 10^5), so a brute-force enumeration of all subarrays is too slow.
Values of nums[i] can be negative or positive, but the problem only requires relative comparisons for peak detection.
The distance condition (i-l <= k and r-i <= k) ensures that valid subarrays are centered around peaks but cannot extend too far.

Key edge cases to watch for:

Arrays with no peaks, where the output should be zero.
Peaks at the boundaries (indices 0 or n-1) are not considered peaks.
Arrays with multiple peaks where overlapping subarrays could exist.

Approaches

Brute-force Approach: Iterate through all possible subarrays of nums, check if they contain exactly one peak, and verify the distance constraints. While this guarantees correctness, the number of subarrays is O(n^2), which is infeasible for n = 10^5.

Optimal Approach: Observe that the valid subarrays are determined entirely by peaks and their distances. For each peak, we can expand left and right up to k steps and count all contiguous subarrays that include the peak exactly once. This reduces the problem to iterating over peaks and calculating the number of valid subarrays using combinatorial counting, rather than explicitly generating all subarrays.

Key insight:

For a peak at index i, the maximum left index of the subarray is max(i - k, 0) and the maximum right index is min(i + k, n-1).
The number of subarrays including the peak is the product of the number of choices for the left end and the number of choices for the right end.
We can compute these in O(1) per peak, leading to an overall O(n) algorithm.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Iterate all subarrays, check peak and distance constraints
Optimal	O(n)	O(1)	Iterate peaks, compute valid subarray counts using distances

Algorithm Walkthrough

Initialize a variable count to 0 to track the number of valid subarrays.
Iterate over the array from index 1 to n-2 (ignoring boundaries since they cannot be peaks).
For each index i, check if nums[i] is a peak (nums[i] > nums[i-1] and nums[i] > nums[i+1]).
If it is a peak, compute the maximum left extent as max(i - k, 0) and the maximum right extent as min(i + k, n-1).
The number of valid subarrays for this peak is (i - left + 1) * (right - i + 1) because any choice of left and right endpoints within the allowed distances forms a valid subarray.
Add this count to the global count.
Return count after processing all indices.

Why it works: Each peak independently determines a set of valid subarrays constrained by k. Since a valid subarray must contain exactly one peak, counting subarrays centered around each peak separately guarantees correctness. Overlaps are naturally handled because each peak's contribution is isolated.

Python Solution

class Solution:
    def validSubarrays(self, nums: list[int], k: int) -> int:
        n = len(nums)
        count = 0
        
        for i in range(1, n - 1):
            if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
                left = max(i - k, 0)
                right = min(i + k, n - 1)
                count += (i - left + 1) * (right - i + 1)
        
        return count

Explanation: We iterate through all possible peak candidates, check the peak condition, calculate the allowed subarray extents based on k, and count all subarrays including this peak. This uses only O(1) extra space and O(n) time since each element is visited once.

Go Solution

func validSubarrays(nums []int, k int) int64 {
    n := len(nums)
    var count int64 = 0

    for i := 1; i < n-1; i++ {
        if nums[i] > nums[i-1] && nums[i] > nums[i+1] {
            left := i - k
            if left < 0 {
                left = 0
            }
            right := i + k
            if right >= n {
                right = n - 1
            }
            count += int64(i-left+1) * int64(right-i+1)
        }
    }
    return count
}

Go-specific notes: We use int64 to avoid potential overflow since subarray counts can be large. Bounds checking for left and right mirrors the Python logic.

Worked Examples

Example 1: nums = [1,3,2], k = 1

Peak at index 1 (nums[1] = 3)
Left extent: max(1-1, 0) = 0
Right extent: min(1+1, 2) = 2
Valid subarrays: (1-0+1) * (2-1+1) = 2 * 2 = 4

Subarrays: [3], [1,3], [3,2], [1,3,2]

Example 2: nums = [7,8,9], k = 2

No peaks (index 1 is not greater than neighbors)
Count = 0

Example 3: nums = [4,3,5,1], k = 2

Peak at index 2 (nums[2] = 5)
Left extent: max(2-2, 0) = 0
Right extent: min(2+2, 3) = 3
Valid subarrays: (2-0+1) * (3-2+1) = 3*2 = 6

Subarrays: [5], [3,5], [5,1], [3,5,1], [4,3,5], [4,3,5,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Iterate once through the array to find peaks and compute subarray counts
Space	O(1)	Only a constant number of variables are used for counting and bounds

The algorithm avoids generating subarrays explicitly, instead using combinatorial counting to stay within linear time.

Test Cases

# Provided examples
assert Solution().validSubarrays([1,3,2], 1) == 4  # single peak, small k
assert Solution().validSubarrays([7,8,9], 2) == 0  # no peaks
assert Solution().validSubarrays([4,3,5,1], 2) == 6  # peak with max k

# Edge cases
assert Solution().validSubarrays([1], 1) == 0  # single element, no peak
assert Solution().validSubarrays([1,2], 1) == 0  # two elements, no peak
assert Solution().validSubarrays([2,1,2,1,2], 1) == 0  # multiple peaks but isolated by k
assert Solution().validSubarrays([1,3,2,4,3,5,4], 1) == 6  # multiple peaks, k = 1
assert Solution().validSubarrays([1,3,2,4,3,5,4], 2) == 14  # multiple peaks, larger k

Test	Why
[1,3,2], k=1	Basic single peak scenario
[7,8,9], k=2	No peaks, should return 0
[4,3,5,1], k=2	Peak not at boundary, larger subarray options
[1]	Single element, no peak possible
[1,2]	Two elements, still no peak
[2,1,2,1,2], k=1	Multiple small peaks, k limits subarray size
[1,3,2,4,3,5,4], k=1	Multiple peaks, small k
[1,3,2