Valid Subarrays With Exactly One Peak solution and explanation
The problem
You are given an integer array nums of length n and an integer k.
An index i is a peak if:
0 < i < n - 1nums[i] > nums[i - 1]andnums[i] > nums[i + 1]
A subarray [l, r] is valid if:
- It contains exactly one peak at index
ifromnums i - l <= kandr - i <= k
Return an integer denoting the number of valid subarrays in nums.
Example 1:
Input: nums = [1,3,2], k = 1
Output: 4
Explanation:
- Index
i = 1is a peak becausenums[1] = 3is greater thannums[0] = 1andnums[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
isuch thatnums[i]is greater than bothnums[i - 1]andnums[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 = 2is a peak becausenums[2] = 5is greater thannums[1] = 3andnums[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] <= 1051 <= k <= n
Approach overview
Problem Overview: You are given an array and need to count subarrays that contain exactly one peak. A peak is an element nums[i] such that nums[i-1] < nums[i] > nums[i+1]. The challenge is efficiently checking every possible subarray while ensuring the peak count is exactly one.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
The most direct method is to generate every possible subarray using two nested loops and then scan the subarray to count peaks. For each candidate subarray [l, r], iterate through its internal indices and check the peak condition nums[i-1] < nums[i] > nums[i+1]. If the count of peaks equals one, increment the answer. This approach is simple but inefficient because each subarray requires another scan, resulting in O(n^3) time.
Approach 2: Simulation with Running Peak Count (O(n^2) time, O(1) space)
A more practical solution still enumerates subarrays but avoids rescanning them repeatedly. Fix a starting index l, then expand the right boundary r one step at a time. As the window grows, only one new candidate position can become a peak. Update a running peak counter whenever the new element completes a nums[i-1] < nums[i] > nums[i+1] pattern. If the peak count becomes greater than one, you can stop expanding that subarray early because any longer subarray will also contain more than one peak. This pruning keeps the approach manageable and results in O(n^2) time with constant space.
Approach 3: Precomputed Peak Array + Simulation (O(n^2) time, O(n) space)
You can precompute an auxiliary array where peak[i] indicates whether index i is a peak. This preprocessing takes O(n) time. When enumerating subarrays, you only check whether the new index contributes a peak by consulting the array instead of recomputing the comparison each time. The enumeration logic stays the same, but peak detection becomes a constant-time lookup. This version trades a small amount of memory for slightly cleaner logic and faster constant factors.
These strategies rely on careful iteration and condition checks, making them good practice for problems involving array patterns and window expansion. The logic is closely related to common techniques used in arrays, simulation, and prefix-style preprocessing often seen in prefix sum problems.
Recommended for interviews: The simulation with running peak count approach is the expected solution. Starting with the brute-force explanation shows you understand the definition of a peak and the structure of the search space. Transitioning to the O(n^2) incremental simulation demonstrates optimization skills by avoiding redundant scans and applying early stopping once multiple peaks appear.
Solution
We first traverse the array to find all peak positions and store them in a list 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.
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 ansclass 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;
}
};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;
}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
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | Useful for understanding the peak definition and validating logic on small inputs |
| Simulation with Running Peak Count | O(n^2) | O(1) | General case solution; avoids rescanning subarrays and allows early stopping |
| Precomputed Peak Array + Simulation | O(n^2) | O(n) | When you want cleaner peak checks with constant-time lookups |
Frequently asked questions
Is Valid Subarrays With Exactly One Peak easy or hard?
The problem is generally classified as Medium. The peak definition is simple, but efficiently counting valid subarrays without repeatedly scanning them requires careful iteration and pruning.
Valid Subarrays With Exactly One Peak Python/Java solution
A typical Python or Java implementation iterates over every starting index and expands the subarray while maintaining a peak counter. Each step checks whether the new element forms a peak with its neighbors and updates the count. The same logic translates directly to C++, Go, and TypeScript.
How to solve Valid Subarrays With Exactly One Peak in O(n)?
A strict O(n) solution is generally not achievable because the number of candidate subarrays is O(n^2). The typical improvement focuses on avoiding rescanning subarrays. By maintaining a running peak counter while expanding the window, you achieve an efficient O(n^2) solution.
What is the best approach for Valid Subarrays With Exactly One Peak?
The most practical approach is simulation with a running peak counter. Fix the left boundary of the subarray and expand the right boundary while tracking how many peak positions appear inside the window. Once the count exceeds one, stop expanding that subarray. This reduces redundant scans and runs in O(n^2) time with O(1) extra space.
Is Valid Subarrays With Exactly One Peak asked at Google/Amazon/Meta?
Array pattern detection and peak-style conditions appear frequently in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, interview questions often involve detecting peaks, valleys, or specific structural patterns within subarrays.
What data structure is used in Valid Subarrays With Exactly One Peak?
The problem primarily uses arrays and simple counters. Some implementations add an auxiliary boolean array to mark peak indices in advance, enabling constant-time checks during subarray expansion.
What is the time complexity of Valid Subarrays With Exactly One Peak?
The optimized simulation solution runs in O(n^2) time because each starting index expands the subarray to the right at most n times. Space complexity is O(1) if peaks are detected on the fly, or O(n) if a precomputed peak array is used.