Problem Description
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.
Key Insights
- An index can be a hill or valley only if it has non-equal neighbors on both sides.
- Hills require the current index to be greater than its neighbors, while valleys require it to be less.
- Adjacent indices with the same value are part of the same hill or valley.
- The solution must efficiently find the closest non-equal neighbors for each index.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
To solve this problem, we can iterate through the array while checking each index (from 1 to n-2) to determine if it qualifies as a hill or valley. For each index, we need to find the closest non-equal neighbors on both sides. If the neighbor values are found, we can then determine if the current index is a hill or a valley. We use a counter to keep track of hills and valleys.