Skip to content

3874. Valid Subarrays With Exactly One Peak πŸ”’

Description

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

An index i is a peak if:

  • 0 < i < n - 1
  • nums[i] > nums[i - 1] and nums[i] > nums[i + 1]

A subarray [l, r] is valid if:

  • It contains exactly one peak at index i from nums
  • i - l <= k and r - i <= k

Return an integer denoting the number of valid subarrays in nums.

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

 

Example 1:

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

Output: 4

Explanation:

  • Index i = 1 is a peak because nums[1] = 3 is greater than nums[0] = 1 and nums[2] = 2.
  • Any valid subarray must include index 1, and the distance from the peak to both ends of the subarray must not exceed k = 1.
  • The valid subarrays are [3], [1, 3], [3, 2], and [1, 3, 2], so the answer is 4.

Example 2:

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

Output: 0

Explanation:

  • There is no index i such that nums[i] is greater than both nums[i - 1] and nums[i + 1].
  • Therefore, the array contains no peak. Thus, the number of valid subarrays is 0.

Example 3:

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

Output: 6

Explanation:

  • Index i = 2 is a peak because nums[2] = 5 is greater than nums[1] = 3 and nums[3] = 1.
  • Any valid subarray must contain this peak, and the distance from the peak to both ends of the subarray must not exceed k = 2.
  • The valid subarrays are [5], [3, 5], [5, 1], [3, 5, 1], [4, 3, 5], and [4, 3, 5, 1], so the answer is 6.

 

Constraints:

  • 1 <= n == nums.length <= 105
  • -105 <= nums[i] <= 105
  • 1 <= k <= n

Solutions

Solution 1: Simulation

Thinking

A valid subarray contains exactly one peak, and that peak lies within \(k\) of both ends. \(n \le 10^5\) forbids enumerating intervals.

Peaks separate one another. For a unique peak \(p\), the left end cannot reach the previous peak, the right end cannot reach the next, and both stay inside \([p-k,p+k]\).

Collect all peaks, then for each peak multiply the number of legal left ends by the number of legal right ends.

Neighboring-peak clamps enforce uniqueness.

We first traverse the array to find all peak positions and store them in a list \(\textit{peaks}\).

For each peak position, we calculate the left and right boundaries centered at the peak with a distance not exceeding \(k\). Note that if there are multiple peaks, we need to ensure the calculated subarray does not contain other peaks. Then, based on the left and right boundaries, we calculate the number of valid subarrays centered at each peak and accumulate it into the answer.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def validSubarrays(self, nums: list[int], k: int) -> int:
        n = len(nums)
        peaks = []
        for i in range(1, n - 1):
            if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
                peaks.append(i)

        ans = 0
        for j, p in enumerate(peaks):
            left_min = max(p - k, 0)
            if j > 0:
                left_min = max(left_min, peaks[j - 1] + 1)

            right_max = min(p + k, n - 1)
            if j < len(peaks) - 1:
                right_max = min(right_max, peaks[j + 1] - 1)

            ans += (p - left_min + 1) * (right_max - p + 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public long validSubarrays(int[] nums, int k) {
        int n = nums.length;
        List<Integer> peaks = new ArrayList<>();

        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                peaks.add(i);
            }
        }

        long ans = 0;
        for (int j = 0; j < peaks.size(); j++) {
            int p = peaks.get(j);

            int leftMin = Math.max(p - k, 0);
            if (j > 0) {
                leftMin = Math.max(leftMin, peaks.get(j - 1) + 1);
            }

            int rightMax = Math.min(p + k, n - 1);
            if (j < peaks.size() - 1) {
                rightMax = Math.min(rightMax, peaks.get(j + 1) - 1);
            }

            ans += (long) (p - leftMin + 1) * (rightMax - p + 1);
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    long long validSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> peaks;

        for (int i = 1; i < n - 1; ++i) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                peaks.push_back(i);
            }
        }

        long long ans = 0;
        for (int j = 0; j < peaks.size(); ++j) {
            int p = peaks[j];

            int leftMin = max(p - k, 0);
            if (j > 0) {
                leftMin = max(leftMin, peaks[j - 1] + 1);
            }

            int rightMax = min(p + k, n - 1);
            if (j < peaks.size() - 1) {
                rightMax = min(rightMax, peaks[j + 1] - 1);
            }

            ans += 1LL * (p - leftMin + 1) * (rightMax - p + 1);
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func validSubarrays(nums []int, k int) int64 {
    n := len(nums)
    peaks := []int{}

    for i := 1; i < n-1; i++ {
        if nums[i] > nums[i-1] && nums[i] > nums[i+1] {
            peaks = append(peaks, i)
        }
    }

    var ans int64
    for j, p := range peaks {
        leftMin := max(p-k, 0)
        if j > 0 {
            leftMin = max(leftMin, peaks[j-1]+1)
        }

        rightMax := min(p+k, n-1)
        if j < len(peaks)-1 {
            rightMax = min(rightMax, peaks[j+1]-1)
        }

        ans += int64(p-leftMin+1) * int64(rightMax-p+1)
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function validSubarrays(nums: number[], k: number): number {
    const n = nums.length;
    const peaks: number[] = [];

    for (let i = 1; i < n - 1; i++) {
        if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
            peaks.push(i);
        }
    }

    let ans = 0;
    for (let j = 0; j < peaks.length; j++) {
        const p = peaks[j];

        let leftMin = Math.max(p - k, 0);
        if (j > 0) {
            leftMin = Math.max(leftMin, peaks[j - 1] + 1);
        }

        let rightMax = Math.min(p + k, n - 1);
        if (j < peaks.length - 1) {
            rightMax = Math.min(rightMax, peaks[j + 1] - 1);
        }

        ans += (p - leftMin + 1) * (rightMax - p + 1);
    }

    return ans;
}

Comments