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.

3874. Valid Subarrays With Exactly One Peak - Practice Online

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