Valid Subarrays With Exactly One Peak - Solution & Explanation

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.