Leetcode 2210. Count Hills and Valleys in an Array
You are given a 0-indexed integer array nums
. An index i
in the array is considered a hill if the following conditions are met:
i > 0
i < nums.length - 1
nums[i] > nums[i - 1]
nums[i] > nums[i + 1]
Similarly, an index i
is considered a valley if the following conditions are met:
i > 0
i < nums.length - 1
nums[i] < nums[i - 1]
nums[i] < nums[i + 1]
Return the number of hills and valleys in nums
.
Q: Can nums
have equal and consecutive elements?
A: Yes, nums
can have consecutive equal elements, but these should not count as hills or valleys.
Q: What is the range of values in the array nums
?
A: The problem will specify that the values fit within a specified range which typically does not affect the logic of counting hills and valleys.
Q: What should be the output if the array nums
has less than three elements?
A: If the array has less than three elements, it is impossible to form a hill or a valley, so the result should be 0.
To solve this problem, we’ll iterate through the nums
list starting from the second element and ending at the second last element (i.e., between indices 1 and nums.length - 2
). For each element, we’ll check the following:
We’ll maintain a counter to keep track of the number of hills and valleys.
count
to 0.nums.length - 2
.Here is the implementation based on the described strategy:
public class Solution {
public int countHillValley(int[] nums) {
if (nums.length < 3) return 0;
int count = 0;
for (int i = 1; i < nums.length - 1; i++) {
if (nums[i] == nums[i - 1]) {
continue;
}
int left = i - 1;
// Move `left` to the leftmost non-equal value in the contiguous range
while (left >= 0 && nums[left] == nums[i - 1]) {
left--;
}
int right = i + 1;
// Move `right` to the rightmost non-equal value in the contiguous range
while (right < nums.length && nums[right] == nums[i + 1]) {
right++;
}
if (left >= 0 && right < nums.length) {
if (nums[i] > nums[left] && nums[i] > nums[right]) {
count++;
} else if (nums[i] < nums[left] && nums[i] < nums[right]) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {2, 4, 1, 1, 6, 5};
System.out.println(solution.countHillValley(nums)); // Output should be 3
}
}
The time complexity of the implemented solution is O(n), where n is the number of elements in the array. This is because we make a single pass through the array while sometimes looking ahead or behind by at most a few steps.
The space complexity is O(1) because we are using a constant amount of extra space.
Got blindsided by a question you didn’t expect?
Spend too much time studying?
Or simply don’t have the time to go over all 3000 questions?