algoadvance

You are given a 0-indexed integer array nums. A hill is a peak element (greater than both of its neighboring elements), and a valley is a trough element (less than both of its neighboring elements). The first and last elements of nums cannot be hills or valleys.

You need to return the number of hills and valleys in nums.

Clarifying Questions

  1. Can the array have duplicate elements? Yes, the array can have duplicate elements.

  2. Should we consider elements with the same value as their neighbors as potential hills or valleys? No, elements with the same value as their neighbors should not be considered as hills or valleys.

  3. What is the range of the array length? The length of nums can range from 1 to 10^5.

  4. What is the range of array elements? The integers in nums can range from -10^5 to 10^5.

Strategy

  1. Iterate through the array:
    • Traverse the array from the second element to the second last element.
    • For each element, check if it is greater than both its neighbors (hill) or less than both its neighbors (valley).
  2. Skip duplicate elements:
    • If the current element is equal to the previous element, continue to the next iteration to avoid unnecessary duplicate checks.
  3. Count hills and valleys:
    • Use a counter to keep track of the number of hills and valleys found.
  4. Return the counter.

Code

def count_hills_and_valleys(nums):
    if len(nums) < 3:
        return 0
    
    count = 0
    
    for i in range(1, len(nums) - 1):
        if nums[i] == nums[i - 1]:
            continue
        
        if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
            count += 1
        elif nums[i] < nums[i - 1] and nums[i] < nums[i + 1]:
            count += 1
    
    return count

# Example usage:
nums = [2, 4, 1, 1, 6, 5]
print(count_hills_and_valleys(nums))  # Output: 2

Explanation of the Code

  1. Boundary Check:
    • If the array has fewer than 3 elements, return 0 (since hills or valleys cannot exist).
  2. Iteration and Skip Duplicates:
    • Loop through the array from index 1 to len(nums) - 2.
    • Skip iterations where the current element is equal to the previous element.
  3. Check for Hills and Valleys:
    • For each element, check if the current element is greater than both the previous and next elements (hill) or less than both the previous and next elements (valley).
    • Increment the count for each hill or valley found.
  4. Returning the Result:
    • Return the count of hills and valleys.

Time Complexity

Try our interview co-pilot at AlgoAdvance.com