Problem Description

LeetCode 2210 asks us to count the number of hills and valleys in an array. A hill is an element that is strictly greater than its neighbors, while a valley is an element that is strictly smaller than its neighbors. The key challenge is handling consecutive duplicate elements - we need to treat them as a single "flat" segment and only consider the boundaries when determining hills and valleys.

Algorithm Walkthrough

The solution uses a single-pass approach with three key variables:

• left: The last distinct value we've processed (acts as the left neighbor)
• right: The next distinct value (acts as the right neighbor)
• count: Running total of hills and valleys found

The algorithm works as follows:

1. Initialize: Set left to the first element and iterate from index 1 to n-2 (since first and last elements can't be hills/valleys)

2. Skip duplicates: When nums[i] == nums[i+1], continue to the next iteration. This ensures we only process positions where the current element differs from the next one.

3. Find right neighbor: Set right = nums[i+1], which gives us the next distinct value.

4. Check hill/valley conditions:

   • Hill: nums[i] > left && nums[i] > right (current element is greater than both neighbors)
   • Valley: nums[i] < left && nums[i] < right (current element is smaller than both neighbors)

5. Update left: Set left = nums[i] to prepare for the next iteration.

The clever part is that by skipping duplicates and only updating left when we find a distinct element, we effectively "compress" consecutive duplicates into single points for comparison purposes.

Complexity Analysis

• Time Complexity: O(n) where n is the length of the array. We make a single pass through the array, and each element is processed at most once.
• Space Complexity: O(1) as we only use a constant amount of extra space for the variables left, right, and count.

Full Solution

Java

class Solution {
    public int countHillValley(int[] nums) {
        int n = nums.length;
        int left = nums[0], right = 0, count = 0;

        for (int i = 1; i < n - 1; i++) {
            // Skip duplicates
            if (nums[i] == nums[i + 1]) {
                continue;
            }

            // Get right neighbor (first different from nums[i])
            right = nums[i + 1];

            // Check hill or valley
            if ((nums[i] > left && nums[i] > right) || 
                (nums[i] < left && nums[i] < right)) {
                count++;
            }

            left = nums[i]; // Update left for next iteration
        }

        return count;
    }
}

C

int countHillValley(int* nums, int numsSize) {
    int left = nums[0], right = 0, count = 0;

    for (int i = 1; i < numsSize - 1; i++) {
        // Skip duplicates
        if (nums[i] == nums[i + 1]) {
            continue;
        }

        // Get right neighbor
        right = nums[i + 1];

        // Check hill or valley
        if ((nums[i] > left && nums[i] > right) || 
            (nums[i] < left && nums[i] < right)) {
            count++;
        }

        left = nums[i];
    }

    return count;
}

C++

class Solution {
public:
    int countHillValley(vector<int>& nums) {
        int n = nums.size();
        int left = nums[0], right = 0, count = 0;

        for (int i = 1; i < n - 1; i++) {
            // Skip duplicates
            if (nums[i] == nums[i + 1]) {
                continue;
            }

            // Get right neighbor
            right = nums[i + 1];

            // Check hill or valley
            if ((nums[i] > left && nums[i] > right) || 
                (nums[i] < left && nums[i] < right)) {
                count++;
            }

            left = nums[i];
        }

        return count;
    }
};

C

public class Solution {
    public int CountHillValley(int[] nums) {
        int n = nums.Length;
        int left = nums[0], right = 0, count = 0;

        for (int i = 1; i < n - 1; i++) {
            // Skip duplicates
            if (nums[i] == nums[i + 1]) {
                continue;
            }

            // Get right neighbor
            right = nums[i + 1];

            // Check hill or valley
            if ((nums[i] > left && nums[i] > right) || 
                (nums[i] < left && nums[i] < right)) {
                count++;
            }

            left = nums[i];
        }

        return count;
    }
}

Python

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        n = len(nums)
        left = nums[0]
        count = 0

        for i in range(1, n - 1):
            # Skip duplicates
            if nums[i] == nums[i + 1]:
                continue

            # Get right neighbor
            right = nums[i + 1]

            # Check hill or valley
            if (nums[i] > left and nums[i] > right) or \
               (nums[i] < left and nums[i] < right):
                count += 1

            left = nums[i]

        return count

Golang

func countHillValley(nums []int) int {
    n := len(nums)
    left := nums[0]
    count := 0

    for i := 1; i < n-1; i++ {
        // Skip duplicates
        if nums[i] == nums[i+1] {
            continue
        }

        // Get right neighbor
        right := nums[i+1]

        // Check hill or valley
        if (nums[i] > left && nums[i] > right) || 
           (nums[i] < left && nums[i] < right) {
            count++
        }

        left = nums[i]
    }

    return count
}