Problem

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

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: nums = [2,4,1,1,6,5]
Output: 3
Explanation:
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 < 4 and 1 < 6, index 2 is a valley.
At index 3: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 3 is a valley, but note that it is part of the same valley as index 2.
At index 4: The closest non-equal neighbors of 6 are 1 and 5. Since 6 > 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: nums = [6,6,5,5,4,1]
Output: 0
Explanation:
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 < 6 and 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 < 6 and 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 < 5 and 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

Method 1 – Single Pass with Skipping Duplicates

Intuition

To find hills and valleys, we need to compare each element to its closest non-equal neighbors on both sides. We skip over consecutive duplicates to ensure we only count each hill or valley once.

Approach

  1. Iterate through the array, skipping consecutive duplicates.
  2. For each index, find the closest non-equal neighbor to the left and right.
  3. If both neighbors exist, check if the current value is greater than both (hill) or less than both (valley).
  4. Count each hill or valley only once.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int countHillValley(vector<int>& nums) {
        int ans = 0, n = nums.size();
        for (int i = 1; i < n - 1; ++i) {
            int l = i - 1, r = i + 1;
            while (l >= 0 && nums[l] == nums[i]) l--;
            while (r < n && nums[r] == nums[i]) r++;
            if (l >= 0 && r < n) {
                if ((nums[i] > nums[l] && nums[i] > nums[r]) || (nums[i] < nums[l] && nums[i] < nums[r]))
                    ans++;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func countHillValley(nums []int) int {
    ans, n := 0, len(nums)
    for i := 1; i < n-1; i++ {
        l, r := i-1, i+1
        for l >= 0 && nums[l] == nums[i] { l-- }
        for r < n && nums[r] == nums[i] { r++ }
        if l >= 0 && r < n {
            if (nums[i] > nums[l] && nums[i] > nums[r]) || (nums[i] < nums[l] && nums[i] < nums[r]) {
                ans++
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int countHillValley(int[] nums) {
        int ans = 0, n = nums.length;
        for (int i = 1; i < n - 1; i++) {
            int l = i - 1, r = i + 1;
            while (l >= 0 && nums[l] == nums[i]) l--;
            while (r < n && nums[r] == nums[i]) r++;
            if (l >= 0 && r < n) {
                if ((nums[i] > nums[l] && nums[i] > nums[r]) || (nums[i] < nums[l] && nums[i] < nums[r]))
                    ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun countHillValley(nums: IntArray): Int {
        var ans = 0
        val n = nums.size
        for (i in 1 until n-1) {
            var l = i-1
            var r = i+1
            while (l >= 0 && nums[l] == nums[i]) l--
            while (r < n && nums[r] == nums[i]) r++
            if (l >= 0 && r < n) {
                if ((nums[i] > nums[l] && nums[i] > nums[r]) || (nums[i] < nums[l] && nums[i] < nums[r]))
                    ans++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def countHillValley(self, nums: list[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(1, n-1):
            l, r = i-1, i+1
            while l >= 0 and nums[l] == nums[i]: l -= 1
            while r < n and nums[r] == nums[i]: r += 1
            if l >= 0 and r < n:
                if (nums[i] > nums[l] and nums[i] > nums[r]) or (nums[i] < nums[l] and nums[i] < nums[r]):
                    ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn count_hill_valley(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        for i in 1..n-1 {
            let mut l = i as i32 - 1;
            let mut r = i + 1;
            while l >= 0 && nums[l as usize] == nums[i] { l -= 1; }
            while r < n && nums[r] == nums[i] { r += 1; }
            if l >= 0 && r < n as i32 {
                if (nums[i] > nums[l as usize] && nums[i] > nums[r]) || (nums[i] < nums[l as usize] && nums[i] < nums[r]) {
                    ans += 1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    countHillValley(nums: number[]): number {
        let ans = 0, n = nums.length;
        for (let i = 1; i < n - 1; i++) {
            let l = i - 1, r = i + 1;
            while (l >= 0 && nums[l] === nums[i]) l--;
            while (r < n && nums[r] === nums[i]) r++;
            if (l >= 0 && r < n) {
                if ((nums[i] > nums[l] && nums[i] > nums[r]) || (nums[i] < nums[l] && nums[i] < nums[r]))
                    ans++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array, for a single pass.
  • 🧺 Space complexity: O(1), only a constant amount of space is used.