Count Hills and Valleys in an Array
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
A more efficient approach is to first simplify the array by removing consecutive duplicates. This transforms plateaus into single points, making the identification of hills and valleys straightforward.
Algorithm
- Create a new
ArrayList<Integer>calleddistinctNums. - Add the first element
nums[0]todistinctNums. - Iterate through
numsfrom the second element. Ifnums[i]is not equal to the last element indistinctNums, addnums[i]. - If the size of
distinctNumsis less than 3, return 0. - Initialize
count = 0. - Iterate
ifrom 1 todistinctNums.size() - 2. - Check if
distinctNums.get(i)is a hill or valley compared to its neighborsdistinctNums.get(i-1)anddistinctNums.get(i+1). - If it is, increment
count. - Return
count.
Walkthrough
The core idea is that a plateau like [2, 4, 4, 4, 1] behaves like a single peak [2, 4, 1]. By removing consecutive duplicates, we can simplify the problem.
First, we create a new list. We iterate through the input nums and add an element to our new list only if it's different from the last element added. This effectively filters out all plateaus.
After this pre-processing step, we have a new array where no two adjacent elements are the same.
Then, we can simply iterate through this new array from its second element to its second-to-last element. For each element A[i], we check if it's a hill (A[i-1] < A[i] > A[i+1]) or a valley (A[i-1] > A[i] < A[i+1]).
import java.util.ArrayList;import java.util.List; class Solution { public int countHillValley(int[] nums) { // Step 1: Remove consecutive duplicates List<Integer> distinctNums = new ArrayList<>(); distinctNums.add(nums[0]); for (int i = 1; i < nums.length; i++) { if (nums[i] != nums[i-1]) { distinctNums.add(nums[i]); } } // Step 2: Count hills and valleys in the simplified list if (distinctNums.size() < 3) { return 0; } int count = 0; for (int i = 1; i < distinctNums.size() - 1; i++) { int left = distinctNums.get(i - 1); int middle = distinctNums.get(i); int right = distinctNums.get(i + 1); if (middle > left && middle > right) { count++; // Hill } else if (middle < left && middle < right) { count++; // Valley } } return count; }}Complexity
Time
O(N) because we iterate through the original array once to build the new list and then iterate through the new list (at most `N` elements) once.
Space
O(N) in the worst case, as the new list could potentially store all elements if there are no consecutive duplicates.
Trade-offs
Pros
Much faster than the brute-force approach with a linear time complexity.
The logic is clean and easy to follow once the array is simplified.
Cons
Requires extra space proportional to the number of elements in the worst case.
Solutions
Solution
class Solution {public int countHillValley(int[] nums) { int ans = 0; for (int i = 1, j = 0; i < nums.length - 1; ++i) { if (nums[i] == nums[i + 1]) { continue; } if (nums[i] > nums[j] && nums[i] > nums[i + 1]) { ++ans; } if (nums[i] < nums[j] && nums[i] < nums[i + 1]) { ++ans; } j = i; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.