Count Hills and Valleys in an Array - Solution & Explanation
Problem Statement
You are given a 0-indexed integer array nums. An index i is part of a hill in nums if the closest non-equal neighbors of i are smaller than nums[i]. Similarly, an index i is part of a valley in nums if the closest non-equal neighbors of i are larger than nums[i]. Adjacent indices i and j are part of the same hill or valley if nums[i] == nums[j].
Note that for an index to be part of a hill or valley, it must have a non-equal neighbor on both the left and right of the index.
Return the number of hills and valleys in nums.
Example 1:
Input: nums = [2,4,1,1,6,5] Output: 3 Explanation: At index 0: There is no non-equal neighbor of 2 on the left, so index 0 is neither a hill nor a valley. At index 1: The closest non-equal neighbors of 4 are 2 and 1. Since 4 > 2 and 4 > 1, index 1 is a hill. At index 2: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 2 is a valley. At index 3: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 3 is a valley, but note that it is part of the same valley as index 2. At index 4: The closest non-equal neighbors of 6 are 1 and 5. Since 6 > 1 and 6 > 5, index 4 is a hill. At index 5: There is no non-equal neighbor of 5 on the right, so index 5 is neither a hill nor a valley. There are 3 hills and valleys so we return 3.
Example 2:
Input: nums = [6,6,5,5,4,1] Output: 0 Explanation: At index 0: There is no non-equal neighbor of 6 on the left, so index 0 is neither a hill nor a valley. At index 1: There is no non-equal neighbor of 6 on the left, so index 1 is neither a hill nor a valley. At index 2: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 2 is neither a hill nor a valley. At index 3: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 3 is neither a hill nor a valley. At index 4: The closest non-equal neighbors of 4 are 5 and 1. Since 4 < 5 and 4 > 1, index 4 is neither a hill nor a valley. At index 5: There is no non-equal neighbor of 1 on the right, so index 5 is neither a hill nor a valley. There are 0 hills and valleys so we return 0.
Constraints:
3 <= nums.length <= 1001 <= nums[i] <= 100
Approach Overview
Problem Overview: You’re given an integer array representing heights. A hill occurs when the current value is strictly greater than its nearest different neighbors, and a valley occurs when it is strictly smaller. Consecutive duplicates do not form new terrain changes, so they must be skipped when determining the previous and next values.
Approach 1: Linear Scan with Skip Duplicates (O(n) time, O(1) space)
This approach walks through the array once while ignoring consecutive duplicate values. The key insight is that duplicates should be treated as part of the same plateau, so you only compare the current number with the previous distinct value and the next distinct value. Iterate from index 1 to n-2, skipping duplicates using a loop until a different value appears. If nums[i] is greater than both neighbors, it forms a hill; if it is smaller than both, it forms a valley. Each element is processed at most once, so the time complexity is O(n) and the algorithm uses O(1) extra space.
This technique relies on simple comparisons and sequential iteration, making it ideal for problems focused on terrain patterns in arrays. It’s a common pattern when dealing with plateau-style data where duplicates distort local comparisons. The implementation is straightforward and works efficiently even for large inputs.
Approach 2: Two Pointers (O(n) time, O(1) space)
The two pointers strategy maintains a pointer to the previous distinct value while scanning forward with another pointer. As you iterate through the array, skip duplicate elements until the next different value appears. With pointers positioned at prev, curr, and next, check whether the current value forms a hill or valley. After evaluation, move the prev pointer forward to the last processed distinct value.
This method makes the duplicate skipping logic explicit and keeps comparisons clean. It still performs a single pass through the array, resulting in O(n) time complexity and O(1) auxiliary space. The approach is particularly readable when implementing terrain-style comparisons because each pointer clearly represents a structural role in the sequence.
Problems like this frequently appear in array traversal tasks where local patterns depend on neighboring values. Variants also show up alongside pointer-based traversal strategies such as two pointers or slope detection logic.
Recommended for interviews: The Linear Scan with Skip Duplicates approach is what most interviewers expect. It demonstrates that you understand how duplicates affect local comparisons and how to maintain constant space while scanning the array. Explaining the plateau issue first and then implementing the O(n) scan shows strong problem decomposition skills.
Approach 1: Approach 1: Linear Scan with Skip Duplicates
This approach involves iterating through the list while skipping consecutive duplicate values to identify hills and valleys. We only consider points as potential hills or valleys if their adjacent non-equal neighbors on both sides exist and fulfill the necessary conditions.
This solution iterates through the array and checks if the current element is greater than its neighbors for a hill or lesser for a valley. It counts such instances, skipping repeated elements to avoid over-counting.
Complexity
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1) since we are using a constant amount of extra space.
Approach 2: Approach 2: Two Pointers
This approach employs two pointers to effectively manage non-equal comparisons and avoid redundant checks.
In this C solution, two pointers (left and right) help to skip over duplicates and directly move to the next unique neighbors for comparison.
Complexity
Time Complexity: O(n) where n is the length of the array due to linear traversal and skipping.
Space Complexity: O(1).
Approach 3: Traversal
We initialize a pointer j to point to the position with index 0, and then traverse the array in the range [1, n-1]. For each position i:
- If
nums[i] = nums[i+1], then skip. - Otherwise, if
nums[i]is greater thannums[j]andnums[i]is greater thannums[i+1], theniis a peak; ifnums[i]is less thannums[j]andnums[i]is less thannums[i+1], theniis a valley. - Then, we update
jtoiand continue to traverse.
After the traversal, we can get the number of peaks and valleys.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Linear Scan with Skip Duplicates | Time Complexity: O(n) where n is the length of the array. |
| Approach 2: Two Pointers | Time Complexity: O(n) where n is the length of the array due to linear traversal and skipping. |
| Traversal | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan with Skip Duplicates | O(n) | O(1) | General case. Best approach when you need to detect hills and valleys while ignoring consecutive duplicates. |
| Two Pointers | O(n) | O(1) | When you want clearer control over previous, current, and next distinct values during traversal. |
Video Solution
Count Hills and Valleys in an Array | Simple Explanation | Leetcode 2210 | codestorywithMIK • codestorywithMIK • 6,731 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Hills and Valleys in an Array easy or hard?
Count Hills and Valleys in an Array Python/Java solution
How to solve Count Hills and Valleys in an Array in O(n)?
What is the best approach for Count Hills and Valleys in an Array?
Is Count Hills and Valleys in an Array asked at Google/Amazon/Meta?
What data structure is used in Count Hills and Valleys in an Array?
What is the time complexity of Count Hills and Valleys in an Array?
Ready to solve this problem?
Practice Count Hills and Valleys in an Array with our built-in code editor and test cases.
Practice on FleetCode