Leetcode 2210: Count Hills and Valleys in an Array
grid47 Exploring patterns and algorithms
Mar 31, 2024
5 min read
You are given an integer array ’nums’. A number at index ‘i’ is part of a hill if its closest non-equal neighbors on both sides are smaller than the number at index ‘i’. Similarly, an index ‘i’ is part of a valley if its closest non-equal neighbors on both sides are larger than the number at index ‘i’. Adjacent indices ‘i’ and ‘j’ are part of the same hill or valley if the values at nums[i] and nums[j] are the same. An index must have non-equal neighbors on both sides to be part of a hill or valley. Your task is to count the total number of hills and valleys.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of integers.
Example: nums = [3, 5, 1, 4, 2]
Constraints:
• 3 <= nums.length <= 100
• 1 <= nums[i] <= 100
Output: Return the total number of hills and valleys in the array.
Example: Output: 2
Constraints:
Goal: Identify hills and valleys based on the given conditions.
Steps:
• Iterate through the array and check for each element if it satisfies the hill or valley condition.
• For each element, compare it with the closest non-equal neighbors to determine if it forms a hill or valley.
• Count the number of hills and valleys.
Goal: The array length is between 3 and 100, and each element is between 1 and 100.
Steps:
• 3 <= nums.length <= 100
• 1 <= nums[i] <= 100
Assumptions:
• The input array has at least three elements.
• Input: nums = [3, 5, 1, 4, 2]
• Explanation: In this example, index 1 is a hill (5 > 3 and 5 > 1), index 2 is a valley (1 < 5 and 1 < 4), and index 3 is a hill (4 > 1 and 4 > 2). Therefore, the total count of hills and valleys is 2.
Approach: The approach involves iterating over the array and identifying hills and valleys based on the given conditions. A hill is a number that is greater than both its neighbors, and a valley is smaller than both its neighbors.
Observations:
• A hill is a local maximum, and a valley is a local minimum in the context of non-equal neighbors.
• We can iterate through the array and check for each element if it satisfies the hill or valley conditions.
Steps:
• Loop through the array and check the conditions for hills and valleys at each index.
• For each index, check if it has valid non-equal neighbors on both sides.
• Count the total number of hills and valleys.
Empty Inputs:
• The input array must have at least 3 elements.
Large Inputs:
• The solution should handle arrays of size up to 100 elements efficiently.
Special Values:
• Arrays where all elements are equal will not have any hills or valleys.
Constraints:
intcountHillValley(vector<int>& nums) {
int res =0;
for(int j =0, i =1; i < nums.size() -1; i++)
if ((nums[j] < nums[i] && nums[i] > nums[i +1]) || (nums[j] > nums[i] && nums[i] < nums[i +1])) {
res++;
j = i;
}
return res;
}
1 : Function Definition
intcountHillValley(vector<int>& nums) {
Function definition begins. This function takes a vector of integers as input and will return an integer value.
2 : Variable Initialization
int res =0;
Initialize the result variable `res` to 0. This will store the count of hill and valley points.
3 : Loop Setup
for(int j =0, i =1; i < nums.size() -1; i++)
Start a loop to iterate through the vector `nums`. The loop runs from index 1 to `size - 2` (excluding the first and last element). The variable `j` keeps track of the previous peak or valley.
4 : Condition Check
if ((nums[j] < nums[i] && nums[i] > nums[i +1]) ||
Check if the current point `i` is a 'hill'. A hill occurs when the current element is greater than both its neighbors.
5 : Condition Check
(nums[j] > nums[i] && nums[i] < nums[i +1])) {
Check if the current point `i` is a 'valley'. A valley occurs when the current element is smaller than both its neighbors.
6 : Increment Result
res++;
If the current point is either a hill or valley, increment the result count.
7 : Update Previous Point
j = i;
Update `j` to the current index `i` to track the new reference point for the next hill/valley check.
8 : Return Result
return res;
Return the final count of hills and valleys found in the vector.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We need to loop through each element once, making the time complexity O(n), where n is the length of the input array.
Best Case: O(1)
Worst Case: O(1)
Description: The solution uses a constant amount of extra space since we are only tracking the count of hills and valleys.
