Difference Between Peaks and Valleys solution and explanation
The problem
You are given an integer array nums of length n.
An index i is called a peak if all of the following conditions hold:
0 < i < n - 1nums[i] > nums[i - 1]nums[i] > nums[i + 1]
An index i is called a valley if all of the following conditions hold:
0 < i < n - 1nums[i] < nums[i - 1]nums[i] < nums[i + 1]
Return an integer denoting the difference between the sum of all peak values and the sum of all valley values.
Example 1:
Input: nums = [1,5,2,4,1,3,0]
Output: 9
Explanation:
- The peak values are
nums[1] = 5,nums[3] = 4, andnums[5] = 3. - The valley values are
nums[2] = 2andnums[4] = 1. - The difference between the sum of the peak values and the sum of the valley values is
(5 + 4 + 3) - (2 + 1) = 9. Hence, the answer is 9.
Example 2:
Input: nums = [-5,-6,-1,-2,5,3,2]
Output: 12
Explanation:
- The peak values are
nums[2] = -1andnums[4] = 5. - The valley values are
nums[1] = -6andnums[3] = -2. - The difference between the sum of the peak values and the sum of the valley values is
(-1 + 5) - (-6 + (-2)) = 12. Hence, the answer is 12.
Example 3:
Input: nums = [6,5,2,5,5,3,6]
Output: -5
Explanation:
- There are no peak values in the array.
- The valley values are
nums[2] = 2andnums[5] = 3. - The difference between the sum of the peak values and the sum of the valley values is
(0) - (2 + 3) = -5. Hence, the answer is -5.
Constraints:
3 <= n == nums.length <= 100-100 <= nums[i] <= 100
Approach overview
Problem Overview: Scan the array and classify each interior element as a peak (strictly greater than both neighbors) or a valley (strictly smaller than both neighbors). Return the difference between the values of the peaks and the values of the valleys. The first and last elements never qualify because they have only one neighbor.
Approach 1: Collect Peaks and Valleys in Separate Lists (O(n) time, O(n) space)
Iterate from index 1 to n-2 and check each element against its left and right neighbors. Append qualifying values to a peaks list or a valleys list. After the loop, sum both lists and subtract. This approach is easy to verify because each list mirrors the definition in the problem statement. Use it when you want a clear intermediate result for debugging or when the classification rules get more complex.
Approach 2: Single Pass with Running Sums (O(n) time, O(1) space)
Skip the lists entirely. Keep two integers, peakSum and valleySum, and update them during the same loop that checks neighbors. Each index is visited once, and each comparison uses only nums[i-1], nums[i], and nums[i+1], so no extra storage grows with input size. This is the version you should write in an interview. It is the same array scan as Approach 1, just without the memory overhead.
Approach 3: Brute Force with Repeated Checks (O(n) time, O(1) space)
Some candidates first write a version that re-reads neighbors through helper functions or recomputes boundary conditions for every index with extra branching. The asymptotic cost stays O(n), but the code gets harder to reason about. Treat this as a warm-up, not a target. Simplifying the neighbor checks into one clean loop is the actual skill being tested.
Recommended for interviews: Interviewers expect Approach 2. Writing the list-based version shows you understand the definition of a peak and a valley. Writing the single-pass version with correct boundary handling at indices 1 and n-2 shows you can translate a definition into tight, constant-space code. Mention the boundary rule out loud before you code, since off-by-one errors are the most common failure point. For more practice on this pattern, see two pointers and simulation problems.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Collect Peaks and Valleys in Lists | O(n) | O(n) | Debugging or when you need the actual peak and valley positions |
| Single Pass with Running Sums | O(n) | O(1) | General case and interviews |
| Brute Force with Helper Checks | O(n) | O(1) | First draft only, before refactoring into a single loop |
Frequently asked questions
Is Difference Between Peaks and Valleys easy or hard?
This problem is easy. It requires one linear scan and careful handling of the boundary indices. Most difficulty comes from off-by-one errors at the first and last positions, not from the algorithm itself.
How to solve Difference Between Peaks and Valleys in O(n)?
Loop from index 1 to index n-2, since the first and last elements have only one neighbor. For each index, compare nums[i] with nums[i-1] and nums[i+1]. If it is greater than both, add it to the peak sum. If it is smaller than both, add it to the valley sum, then return the difference.
Difference Between Peaks and Valleys Python or Java solution?
In Python, loop with range(1, len(nums) - 1) and use two integer variables to accumulate peaks and valleys, then return the difference. In Java, use a for loop from i = 1 to i < nums.length - 1 with two long or int accumulators. Both versions run in O(n) time and O(1) space.
What is the best approach for Difference Between Peaks and Valleys?
The best approach is a single pass over the array that updates a peak sum and a valley sum at the same time. Check each interior element against its two neighbors and add it to the correct running total. This runs in O(n) time with O(1) extra space.
What data structure is used in Difference Between Peaks and Valleys?
The problem needs only an array, which is given as input, and two integer variables for the running sums. You do not need a hash map, stack, or heap. Using lists to collect peaks and valleys is an option, but it adds O(n) space that the single-pass solution avoids.
What is the time complexity of Difference Between Peaks and Valleys?
The optimal solution runs in O(n) time because every interior element is visited once and each check uses a constant number of comparisons. The space complexity is O(1) when you use running sums instead of storing peaks and valleys in lists.
Is Difference Between Peaks and Valleys asked at Google, Amazon, or Meta?
This problem is tagged General on FleetCode and does not have a confirmed company tag in the source data. It is a short array-scan problem, so expect it as a warm-up or screening question rather than a hard round. Check company-specific question lists for the latest reports.