Watch 10 video solutions for Count Hills and Valleys in an Array, a easy level problem involving Array. This walkthrough by codestorywithMIK has 6,606 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 100Problem 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 | 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. |