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 <= 10⁵
-10⁵ <= nums[i] <= 10⁵
1 <= k <= n

Solutions

Solution 1: Simulation

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.

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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;
}

3874. Valid Subarrays With Exactly One Peak 🔒

Description

Solutions

Solution 1: Simulation

Comments