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.
This approach iterates through each potential hill or valley candidate and, for each one, performs a search to find its closest non-equal neighbors on the left and right.
Algorithm
- Initialize
count = 0. - Loop
ifrom 1 tonums.length - 2. - If
nums[i]is the same asnums[i-1], skip to the next iteration to avoid recounting plateaus. - Find the left neighbor: Search backwards from
i-1to find the first elementleftValnot equal tonums[i]. - Find the right neighbor: Search forwards from
i+1to find the first elementrightValnot equal tonums[i]. - If both
leftValandrightValneighbors exist:- Check if
(nums[i] > leftVal && nums[i] > rightVal)or(nums[i] < leftVal && nums[i] < rightVal). - If the condition is true, increment
count.
- Check if
- Return
count.
Walkthrough
We iterate through the array from the second element to the second-to-last (i from 1 to n-2), as the endpoints cannot be hills or valleys.
To handle plateaus (like [3, 5, 5, 2]) and count them as a single event, we only consider an element nums[i] if it's different from its preceding element nums[i-1]. This ensures we only evaluate the start of each plateau.
For each such candidate nums[i], we perform two separate searches:
- A backward search from
i-1to find the first elementnums[j]not equal tonums[i]. This is the left neighbor. - A forward search from
i+1to find the first elementnums[k]not equal tonums[i]. This is the right neighbor. If both a left and a right non-equal neighbor are found, we check ifnums[i]is greater than both (a hill) or smaller than both (a valley). If so, we increment our count.
class Solution { public int countHillValley(int[] nums) { int count = 0; int n = nums.length; for (int i = 1; i < n - 1; i++) { // Skip if part of a plateau that has already been considered if (nums[i] == nums[i - 1]) { continue; } // Find the closest non-equal neighbor on the left int left = -1; for (int j = i - 1; j >= 0; j--) { if (nums[j] != nums[i]) { left = nums[j]; break; } } // Find the closest non-equal neighbor on the right int right = -1; for (int j = i + 1; j < n; j++) { if (nums[j] != nums[i]) { right = nums[j]; break; } } // Check for hill or valley condition if (left != -1 && right != -1) { if (nums[i] > left && nums[i] > right) { count++; } else if (nums[i] < left && nums[i] < right) { count++; } } } return count; }}Complexity
Time
O(N^2) in the worst case. The outer loop runs `N` times, and the inner loops for finding neighbors can also run up to `N` times each.
Space
O(1) as we only use a few variables to store the count and neighbors.
Trade-offs
Pros
Simple to conceptualize, directly follows the problem definition.
Uses constant extra space.
Cons
Inefficient due to nested loops, leading to a quadratic time complexity which is slow for large inputs.
This is the most optimal approach. It achieves linear time complexity without using any extra space. It works by iterating through the array and identifying triplets of consecutive, distinct elements to check for hills or valleys.
Algorithm
- Initialize
count = 0andleft = nums[0]. - Loop
ifrom 1 tonums.length - 1. - If
nums[i]is equal toleft, we are on a plateau. Continue to the nexti. - If
nums[i]is different, it's a potential peak/trough. We need to find its right neighbor. - Search for the right neighbor: Start a pointer
jfromi + 1. Whilej < nums.lengthandnums[j] == nums[i], incrementj. - If
jreaches the end of the array, it meansnums[i]has no right non-equal neighbor, so we can stop. - If
jis a valid index, we have our triplet:left,nums[i], andnums[j]. - Check if
nums[i]is a hill (nums[i] > left && nums[i] > nums[j]) or a valley (nums[i] < left && nums[i] < nums[j]). - If it is, increment
count. - Update
left = nums[i]to prepare for the next distinct element. - The main loop continues from the next
i.
Walkthrough
This method simulates the logic of the pre-processing approach but does it in-place, thus avoiding the O(N) space overhead.
We use a variable left to keep track of the value of the previous distinct element. We iterate through the array with a main pointer i.
We start iterating from i = 1. For each nums[i], we compare it with the left value.
If nums[i] is the same as left, it's part of a plateau, and we continue.
If nums[i] is different from left, it's a potential peak or trough. We then need to find the next distinct element to its right. We use a second pointer j starting from i + 1 to find the first nums[j] that is different from nums[i].
If such a right element nums[j] exists, we have a triplet of distinct values: (left, nums[i], nums[j]). We can then apply the hill/valley check.
After checking, we update left to nums[i] and continue the main iteration.
class Solution { public int countHillValley(int[] nums) { int count = 0; int left = nums[0]; for (int i = 1; i < nums.length - 1; i++) { // Find the right neighbor, skipping plateaus int right = nums[i + 1]; if (nums[i] == right) { // If current element is part of a plateau, find the end of it int j = i + 1; while (j < nums.length - 1 && nums[j] == nums[i]) { j++; } right = nums[j]; // Move i to the end of the plateau to avoid redundant checks i = j - 1; } // Check for hill or valley if (nums[i] > left && nums[i] > right) { count++; } else if (nums[i] < left && nums[i] < right) { count++; } // Update left to the current value for the next iteration left = nums[i]; } return count; }}Complexity
Time
O(N). Although there's a nested `while` loop, each element in the array is visited a constant number of times by pointers `i` and `j` combined. The total work is proportional to `N`.
Space
O(1). We only use a few variables to store the count and the `left` value.
Trade-offs
Pros
Most efficient solution in both time and space.
Processes the array in a single pass without modification or extra data structures.
Cons
The logic with multiple pointers can be slightly more complex to reason about compared to the pre-processing approach.
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; }}class Solution {public: int countHillValley(vector<int> &nums) { int ans = 0; for (int i = 1, j = 0; i < nums.size() - 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; }};class Solution: def countHillValley(self, nums: List[int]) -> int: arr = [nums[0]] for v in nums[1:]: if v != arr[- 1]: arr . append(v) return sum((arr[i] < arr[i - 1]) == (arr[i] < arr[i + 1]) for i in range(1, len(arr) - 1))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.