#2210

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Count Hills and Valleys in an Array

Count Hills and Valleys in an Array determines the number of hills and valleys in a given array by analyzing index neighbors.

array

Problem Statement

You are given a 0-indexed integer array nums. An index i is part of a hill in nums if both of its closest non-equal neighbors are smaller than nums[i]. Similarly, an index i is part of a valley in nums if both of its closest non-equal neighbors are larger than nums[i]. Indices that have equal neighbors do not qualify as hills or valleys. Adjacent indices with the same value are treated as part of the same hill or valley.

To count the hills and valleys in nums, check each index to see if it qualifies based on its neighboring elements. Note that for an index to be considered a hill or valley, it must have non-equal neighbors on both sides. Return the total number of hills and valleys in the array.

Examples

Example 1

Input: nums = [2,4,1,1,6,5]

Output: 3

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 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

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 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 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 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 <= 100
1 <= nums[i] <= 100

Solution Approach

Traverse the Array

Iterate through the array from the second element to the second-to-last element, checking if each element qualifies as a hill or valley based on its non-equal neighbors. Ensure to skip equal adjacent elements to avoid false classifications.

Neighbor Comparison

For each index, compare the element with its neighbors. If both neighbors are smaller, it is a hill. If both neighbors are larger, it is a valley. Ensure the left and right neighbors are non-equal for valid comparisons.

Edge Case Handling

Handle edge cases where an element has no valid non-equal neighbors on one side (first or last element in the array). Skip these indices since they cannot form hills or valleys.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(1)

The time complexity is O(n) as we traverse the array once and perform constant-time operations for each element. The space complexity is O(1) since we only need a few variables for counting the hills and valleys, without using any extra space dependent on the array size.

What Interviewers Usually Probe

Look for the candidate's ability to efficiently check neighbor conditions without iterating unnecessarily.
Assess how well they handle edge cases, like arrays where no hills or valleys exist.
Evaluate their understanding of traversing arrays and managing boundaries while avoiding extra memory usage.

Common Pitfalls or Variants

Common pitfalls

Confusing equal adjacent elements as hills or valleys when they should be skipped.
Overcomplicating the algorithm by adding unnecessary loops or checks.
Forgetting to account for boundary elements (first and last elements) that lack both left and right neighbors.

Follow-up variants

Count only valleys (non-hill elements).
Return the total number of hills and valleys as separate counts.
Modify the problem to identify peaks (strictly larger than both neighbors) and valleys (strictly smaller than both neighbors).

FAQ

What is a hill in the "Count Hills and Valleys in an Array" problem?

A hill is an index in the array where both neighbors are smaller than the current element. The index is considered part of a hill only if the neighbors are non-equal.

How do you define a valley in this problem?

A valley is an index in the array where both neighbors are larger than the current element. Like a hill, the index must have non-equal neighbors on both sides.

What happens if the neighbors are equal in the "Count Hills and Valleys in an Array" problem?

If the neighbors are equal, the index is not considered part of a hill or valley. Only non-equal neighbors qualify for hill or valley classification.

Can the first or last elements of the array be hills or valleys?

No, because they lack both left and right neighbors. A hill or valley requires two non-equal neighbors, so these boundary elements are excluded.

How do you optimize the solution for "Count Hills and Valleys in an Array"?

By traversing the array once and checking each element's neighbors in constant time, the solution achieves O(n) time complexity. No additional space is required, making the space complexity O(1).

terminal

Solution

Solution 1: Traversal

We initialize a pointer $j$ to point to the position with index $0$, and then traverse the array in the range $[1, n-1]$. For each position $i$:

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        ans = j = 0
        for i in range(1, len(nums) - 1):
            if nums[i] == nums[i + 1]:
                continue
            if nums[i] > nums[j] and nums[i] > nums[i + 1]:
                ans += 1
            if nums[i] < nums[j] and nums[i] < nums[i + 1]:
                ans += 1
            j = i
        return ans

Continue Practicing

#2208 minimum operations to halve array sum #2212 maximum points in an archery competition #2213 longest substring of one repeating character