3874. Valid Subarrays With Exactly One Peak 🔒

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums of length n and an integer k.

An index i is called a peak if it satisfies both of the following conditions:

0 < i < n - 1 (the index is strictly inside the array, not at either end)
nums[i] > nums[i - 1] and nums[i] > nums[i + 1] (the value is strictly greater than both of its immediate neighbors)

A subarray [l, r] (the contiguous portion of nums from index l to index r) is considered valid if it meets all of these requirements:

It contains exactly one peak, located at index i
The peak is not too far from the left boundary: i - l <= k
The peak is not too far from the right boundary: r - i <= k

Your task is to return an integer representing the total number of valid subarrays in nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Find all peaks in one pass, then for each peak multiply independent left/right endpoint choices within distance and peak-exclusion bounds.

Open in Flowchart

Intuition

The key observation is that every valid subarray must contain exactly one peak. This means each valid subarray is "anchored" by a single peak. So instead of checking all possible subarrays, we can focus on each peak individually and count how many valid subarrays are centered around it.

Once we fix a peak at index p, a valid subarray [l, r] must satisfy:

l is to the left of (or equal to) p, with p - l <= k, meaning l can range from p - k up to p.
r is to the right of (or equal to) p, with r - p <= k, meaning r can range from p up to p + k.

This gives us a natural way to count: the number of choices for l multiplied by the number of choices for r equals the number of valid subarrays for that peak.

However, we must be careful about two things:

Array bounds. The left index l cannot go below 0, and the right index r cannot go beyond n - 1. So we clamp the ranges using max(p - k, 0) and min(p + k, n - 1).
Exactly one peak. A valid subarray must not include any other peak. If there is a previous peak at peaks[j - 1], then l must stay to the right of it, so l >= peaks[j - 1] + 1. Likewise, if there is a next peak at peaks[j + 1], then r must stay to its left, so r <= peaks[j + 1] - 1. This guarantees the subarray captures only the current peak.

After computing the adjusted left boundary left_min and right boundary right_max for each peak, the number of valid subarrays for that peak is (p - left_min + 1) * (right_max - p + 1). We sum this value over all peaks to get the final answer.

The reason multiplication works here is that the choice of l and the choice of r are completely independent — any valid left endpoint can be paired with any valid right endpoint to form a distinct valid subarray.

Pattern Learn more about Math patterns.

Solution Approach

Solution 1: Simulation

Step 1: Find all peaks.

We first traverse the array from index 1 to n - 2 (since a peak cannot be at either end). For each index i, we check whether nums[i] > nums[i - 1] and nums[i] > nums[i + 1]. If both hold, i is a peak, and we store it in a list peaks. This list keeps the peak positions in increasing order, which makes it easy to look up neighboring peaks later.

Step 2: Count valid subarrays for each peak.

We iterate over the peaks list using both its index j and the peak position p. For each peak, we determine the valid range of left endpoints and right endpoints:

Left boundary left_min:
- Start with max(p - k, 0) to respect both the distance limit k and the array's left bound 0.
- If there is a previous peak (j > 0), the left endpoint must not reach past it, so we update left_min = max(left_min, peaks[j - 1] + 1). This ensures the subarray excludes the previous peak.
Right boundary right_max:
- Start with min(p + k, n - 1) to respect both the distance limit k and the array's right bound n - 1.
- If there is a next peak (j < len(peaks) - 1), the right endpoint must not reach it, so we update right_max = min(right_max, peaks[j + 1] - 1). This ensures the subarray excludes the next peak.

Step 3: Apply the multiplication principle.

For the current peak p:

The number of valid left endpoints is p - left_min + 1.
The number of valid right endpoints is right_max - p + 1.

Since choosing l and r are independent, the number of valid subarrays centered at p is the product:

(p - left_min + 1) * (right_max - p + 1)

We add this to the answer ans.

Step 4: Return the result.

After processing every peak, ans holds the total count of valid subarrays, which we return.

Complexity Analysis:

Time complexity: O(n), where n is the length of nums. We make one pass to collect the peaks and one pass over the peaks (at most n of them) to count subarrays.
Space complexity: O(n) in the worst case, for storing the peaks list. Although note that peaks cannot be adjacent, so the list holds at most about n / 2 elements.

Example Walkthrough

Let's trace through the solution with a concrete example.

Input: nums = [1, 3, 1, 5, 1, 4, 1], k = 2, so n = 7.

Step 1: Find all peaks.

We scan indices 1 through n - 2 = 5, checking whether nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:

`i`	`nums[i-1]`	`nums[i]`	`nums[i+1]`	Peak?
1	1	3	1	✅ Yes (`3 > 1` and `3 > 1`)
2	3	1	5	❌ No
3	1	5	1	✅ Yes (`5 > 1` and `5 > 1`)
4	5	1	4	❌ No
5	1	4	1	✅ Yes (`4 > 1` and `4 > 1`)

So peaks = [1, 3, 5].

Step 2 & 3: Count valid subarrays for each peak.

We process each peak, computing left_min, right_max, then multiplying the counts.

Peak j = 0, p = 1:

left_min = max(p - k, 0) = max(1 - 2, 0) = 0
No previous peak (j = 0), so left_min stays 0.
right_max = min(p + k, n - 1) = min(1 + 2, 6) = 3
Next peak exists at peaks[1] = 3, so right_max = min(3, 3 - 1) = 2.
Left choices: p - left_min + 1 = 1 - 0 + 1 = 2 (i.e., l ∈ {0, 1})
Right choices: right_max - p + 1 = 2 - 1 + 1 = 2 (i.e., r ∈ {1, 2})
Subarrays: 2 * 2 = 4

Peak j = 1, p = 3:

left_min = max(3 - 2, 0) = 1
Previous peak at peaks[0] = 1, so left_min = max(1, 1 + 1) = 2.
right_max = min(3 + 2, 6) = 5
Next peak at peaks[2] = 5, so right_max = min(5, 5 - 1) = 4.
Left choices: 3 - 2 + 1 = 2 (i.e., l ∈ {2, 3})
Right choices: 4 - 3 + 1 = 2 (i.e., r ∈ {3, 4})
Subarrays: 2 * 2 = 4

Peak j = 2, p = 5:

left_min = max(5 - 2, 0) = 3
Previous peak at peaks[1] = 3, so left_min = max(3, 3 + 1) = 4.
right_max = min(5 + 2, 6) = 6
No next peak (j is the last index), so right_max stays 6.
Left choices: 5 - 4 + 1 = 2 (i.e., l ∈ {4, 5})
Right choices: 6 - 5 + 1 = 2 (i.e., r ∈ {5, 6})
Subarrays: 2 * 2 = 4

Step 4: Sum the results.

ans = 4 + 4 + 4 = 12.

Verification (spot check for peak p = 1):

The four valid subarrays are formed by pairing l ∈ {0, 1} with r ∈ {1, 2}:

[0, 1] → [1, 3] — contains only peak 1 ✅
[0, 2] → [1, 3, 1] — contains only peak 1 ✅
[1, 1] → [3] — single element, contains peak 1 ✅
[1, 2] → [3, 1] — contains only peak 1 ✅

Notice the boundaries did their job: right_max was clamped to 2 so we never extended to index 3 (the next peak), keeping exactly one peak per subarray.

Final answer: 12.

Solution Implementation

1class Solution:
2    def validSubarrays(self, nums: list[int], k: int) -> int:
3        n = len(nums)
4
5        # Step 1: Find all peak indices.
6        # A peak is an element strictly greater than both of its neighbors.
7        # Endpoints (index 0 and n-1) cannot be peaks since they lack a neighbor.
8        peak_indices: list[int] = []
9        for i in range(1, n - 1):
10            if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
11                peak_indices.append(i)
12
13        # Step 2: For each peak, count subarrays that contain exactly this peak.
14        # A valid subarray must:
15        #   - include the current peak,
16        #   - extend at most k positions to the left/right of the peak,
17        #   - not include any other peak.
18        total = 0
19        for current, peak in enumerate(peak_indices):
20            # Leftmost allowed start index:
21            # bounded by the k-distance limit and the array's left edge.
22            left_bound = max(peak - k, 0)
23            # Must also stay to the right of the previous peak (exclusive),
24            # so this subarray does not contain that previous peak.
25            if current > 0:
26                left_bound = max(left_bound, peak_indices[current - 1] + 1)
27
28            # Rightmost allowed end index:
29            # bounded by the k-distance limit and the array's right edge.
30            right_bound = min(peak + k, n - 1)
31            # Must also stay to the left of the next peak (exclusive),
32            # so this subarray does not contain that next peak.
33            if current < len(peak_indices) - 1:
34                right_bound = min(right_bound, peak_indices[current + 1] - 1)
35
36            # Number of choices for the start endpoint multiplied by
37            # the number of choices for the end endpoint.
38            left_choices = peak - left_bound + 1
39            right_choices = right_bound - peak + 1
40            total += left_choices * right_choices
41
42        return total
43

1class Solution {
2    /**
3     * Counts the number of subarrays that contain exactly one peak,
4     * where the peak's index is at most k positions away from both
5     * endpoints of the subarray.
6     *
7     * A peak is an element strictly greater than both of its neighbors.
8     *
9     * @param nums the input array
10     * @param k    the maximum allowed distance from the peak to either endpoint
11     * @return the total count of valid subarrays
12     */
13    public long validSubarrays(int[] nums, int k) {
14        int n = nums.length;
15
16        // Collect the indices of all peaks in the array.
17        // A peak cannot be the first or last element since it needs both neighbors.
18        List<Integer> peaks = new ArrayList<>();
19        for (int i = 1; i < n - 1; i++) {
20            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
21                peaks.add(i);
22            }
23        }
24
25        long ans = 0;
26
27        // For each peak, count how many valid subarrays have this peak as their
28        // single peak. We compute the valid range of left endpoints and right
29        // endpoints independently, then multiply the two counts.
30        for (int j = 0; j < peaks.size(); j++) {
31            int p = peaks.get(j);
32
33            // The leftmost endpoint is bounded by:
34            //   - the distance constraint k (cannot go further left than p - k)
35            //   - array bounds (index 0)
36            //   - the previous peak (left endpoint must come after it so that
37            //     this subarray contains only one peak)
38            int leftMin = Math.max(p - k, 0);
39            if (j > 0) {
40                leftMin = Math.max(leftMin, peaks.get(j - 1) + 1);
41            }
42
43            // The rightmost endpoint is bounded by:
44            //   - the distance constraint k (cannot go further right than p + k)
45            //   - array bounds (index n - 1)
46            //   - the next peak (right endpoint must come before it so that
47            //     this subarray contains only one peak)
48            int rightMax = Math.min(p + k, n - 1);
49            if (j < peaks.size() - 1) {
50                rightMax = Math.min(rightMax, peaks.get(j + 1) - 1);
51            }
52
53            // Number of choices for the left endpoint times the number of choices
54            // for the right endpoint gives all valid subarrays for this peak.
55            long leftChoices = p - leftMin + 1;
56            long rightChoices = rightMax - p + 1;
57            ans += leftChoices * rightChoices;
58        }
59
60        return ans;
61    }
62}
63

1class Solution {
2public:
3    long long validSubarrays(vector<int>& nums, int k) {
4        int n = nums.size();
5
6        // Collect indices of all "peaks": elements strictly greater than
7        // both their immediate neighbors. Endpoints can't be peaks since
8        // they lack one neighbor.
9        vector<int> peaks;
10        for (int i = 1; i < n - 1; ++i) {
11            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
12                peaks.push_back(i);
13            }
14        }
15
16        long long ans = 0;
17        int peakCount = static_cast<int>(peaks.size());
18
19        // For each peak, count the subarrays that contain this peak as their
20        // only peak. We independently determine how far the subarray's left
21        // boundary can extend to the left, and how far the right boundary can
22        // extend to the right.
23        for (int j = 0; j < peakCount; ++j) {
24            int p = peaks[j];
25
26            // Left boundary: bounded by k steps to the left and by the array
27            // start. It must also stay to the right of the previous peak so
28            // that the previous peak is not included.
29            int leftMin = max(p - k, 0);
30            if (j > 0) {
31                leftMin = max(leftMin, peaks[j - 1] + 1);
32            }
33
34            // Right boundary: bounded by k steps to the right and by the array
35            // end. It must also stay to the left of the next peak so that the
36            // next peak is not included.
37            int rightMax = min(p + k, n - 1);
38            if (j < peakCount - 1) {
39                rightMax = min(rightMax, peaks[j + 1] - 1);
40            }
41
42            // Number of valid left endpoints times number of valid right
43            // endpoints gives the count of subarrays centered on this peak.
44            long long leftChoices = static_cast<long long>(p - leftMin + 1);
45            long long rightChoices = static_cast<long long>(rightMax - p + 1);
46            ans += leftChoices * rightChoices;
47        }
48
49        return ans;
50    }
51};
52

1/**
2 * Counts the number of valid subarrays that contain exactly one peak.
3 * A peak is an element strictly greater than both its immediate neighbors.
4 * Each peak's subarray may extend at most `k` positions to either side,
5 * and must not include an adjacent peak.
6 *
7 * @param nums - The input array of numbers.
8 * @param k - The maximum distance a subarray can extend from a peak on each side.
9 * @returns The total number of valid subarrays.
10 */
11function validSubarrays(nums: number[], k: number): number {
12    const length: number = nums.length;
13
14    // Collect indices of all peak elements (strictly greater than both neighbors).
15    const peakIndices: number[] = [];
16    for (let i = 1; i < length - 1; i++) {
17        if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
18            peakIndices.push(i);
19        }
20    }
21
22    let totalCount: number = 0;
23
24    // For each peak, compute how many valid subarrays have it as the single peak.
25    for (let j = 0; j < peakIndices.length; j++) {
26        const peakIndex: number = peakIndices[j];
27
28        // Determine the leftmost boundary the subarray can reach.
29        // Bounded by k positions to the left and the array start.
30        let leftBoundary: number = Math.max(peakIndex - k, 0);
31        // Must not cross into the previous peak's territory.
32        if (j > 0) {
33            leftBoundary = Math.max(leftBoundary, peakIndices[j - 1] + 1);
34        }
35
36        // Determine the rightmost boundary the subarray can reach.
37        // Bounded by k positions to the right and the array end.
38        let rightBoundary: number = Math.min(peakIndex + k, length - 1);
39        // Must not cross into the next peak's territory.
40        if (j < peakIndices.length - 1) {
41            rightBoundary = Math.min(rightBoundary, peakIndices[j + 1] - 1);
42        }
43
44        // Number of choices for the left endpoint times choices for the right endpoint.
45        const leftChoices: number = peakIndex - leftBoundary + 1;
46        const rightChoices: number = rightBoundary - peakIndex + 1;
47        totalCount += leftChoices * rightChoices;
48    }
49
50    return totalCount;
51}
52

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The first loop scans positions from index 1 to n - 2 to identify all peaks, costing O(n). The second loop iterates over the peaks list, and since the number of peaks is at most O(n), this loop also costs O(n). Each iteration performs only constant-time operations (computing left_min, right_max, and accumulating into ans). Therefore, the overall time complexity is O(n).
Space Complexity: O(n), where n is the length of the array nums. The additional space is dominated by the peaks list, which stores the indices of all peak elements. In the worst case (e.g., an alternating sequence), the number of peaks can be on the order of O(n), so the space complexity is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Allowing a Neighboring Peak to Sneak Into the Subarray

The trickiest part of this problem is the requirement that a valid subarray contains exactly one peak. A very natural mistake is to bound the left/right endpoints only by the distance limit k and the array edges, while forgetting that another peak might fall within that range.

Buggy version:

for current, peak in enumerate(peak_indices):
    left_bound  = max(peak - k, 0)
    right_bound = min(peak + k, n - 1)        # ❌ ignores neighboring peaks
    total += (peak - left_bound + 1) * (right_bound - peak + 1)

Why it fails: Suppose nums = [1, 3, 1, 4, 1] with k = 3. Peaks are at indices 1 and 3. For the peak at index 1, right_bound becomes min(1 + 3, 4) = 4, which means the subarray could extend to index 3 — but index 3 is also a peak. Such a subarray would contain two peaks and must not be counted.

Solution: Clamp the boundaries against the neighboring peaks so the window can never reach them:

if current > 0:
    left_bound = max(left_bound, peak_indices[current - 1] + 1)
if current < len(peak_indices) - 1:
    right_bound = min(right_bound, peak_indices[current + 1] - 1)

The + 1 and - 1 are essential — using peak_indices[current - 1] (without + 1) would still include the previous peak.

Pitfall 2: Confusing the Distance Constraint Direction

The constraints i - l <= k and r - i <= k limit how far the boundaries can be from the peak, not the total subarray length. A common slip is to interpret k as the maximum subarray length (r - l <= k), which produces an entirely different count.

Solution: Keep the two sides independent. The left endpoint may be up to k away and the right endpoint may be up to k away simultaneously, so the maximum span is actually 2k + 1, not k. Treat the left and right choices as independent factors and multiply them.

Pitfall 3: Forgetting Endpoints Can Never Be Peaks

By definition a peak satisfies 0 < i < n - 1. If you scan with range(0, n) and access nums[i - 1] or nums[i + 1], you will trigger an index-out-of-range error (or, with wrap-around indexing like nums[-1], silently produce wrong peaks at the edges).

Solution: Restrict the scan to the strict interior:

for i in range(1, n - 1):   # never touches index 0 or n-1
    ...

This both prevents out-of-bounds access and automatically enforces the rule that endpoints are not peaks.

Pitfall 4: Off-by-One When Counting Endpoint Choices

The number of integers in the inclusive range [left_bound, peak] is peak - left_bound + 1, not peak - left_bound. Dropping the + 1 undercounts every peak's contribution, and worse, would yield 0 whenever a boundary is forced to coincide with the peak itself (e.g., when k = 0 or a neighboring peak is adjacent).

Solution: Always use the inclusive-count formula:

left_choices  = peak - left_bound + 1
right_choices = right_bound - peak + 1

Because the peak position is itself a valid endpoint on both sides, each factor is guaranteed to be at least 1, so the product is never spuriously zero for a genuine peak.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: