# Count Hills and Valleys in an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-hills-and-valleys-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/count-hills-and-valleys-in-an-array
**Data structures:** Array
---
## 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 in_ `nums`.

**Example 1:**

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

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

# Approaches
## Brute Force with Nested Searches
This approach iterates through each potential hill or valley candidate and, for each one, performs a search to find its closest non-equal neighbors on the left and right.
**Time:** O(N^2) in the worst case. The outer loop runs `N` times, and the inner loops for finding neighbors can also run up to `N` times each. · **Space:** O(1) as we only use a few variables to store the count and neighbors.
**Pros:** Simple to conceptualize, directly follows the problem definition.; Uses constant extra space.
**Cons:** Inefficient due to nested loops, leading to a quadratic time complexity which is slow for large inputs.
### Explanation
We iterate through the array from the second element to the second-to-last (`i` from 1 to `n-2`), as the endpoints cannot be hills or valleys.
To handle plateaus (like `[3, 5, 5, 2]`) and count them as a single event, we only consider an element `nums[i]` if it's different from its preceding element `nums[i-1]`. This ensures we only evaluate the start of each plateau.
For each such candidate `nums[i]`, we perform two separate searches:
- A backward search from `i-1` to find the first element `nums[j]` not equal to `nums[i]`. This is the left neighbor.
- A forward search from `i+1` to find the first element `nums[k]` not equal to `nums[i]`. This is the right neighbor.
If both a left and a right non-equal neighbor are found, we check if `nums[i]` is greater than both (a hill) or smaller than both (a valley). If so, we increment our count.

```java
class Solution {
    public int countHillValley(int[] nums) {
        int count = 0;
        int n = nums.length;

        for (int i = 1; i < n - 1; i++) {
            // Skip if part of a plateau that has already been considered
            if (nums[i] == nums[i - 1]) {
                continue;
            }

            // Find the closest non-equal neighbor on the left
            int left = -1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] != nums[i]) {
                    left = nums[j];
                    break;
                }
            }

            // Find the closest non-equal neighbor on the right
            int right = -1;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] != nums[i]) {
                    right = nums[j];
                    break;
                }
            }

            // Check for hill or valley condition
            if (left != -1 && right != -1) {
                if (nums[i] > left && nums[i] > right) {
                    count++;
                } else if (nums[i] < left && nums[i] < right) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0`.
- Loop `i` from 1 to `nums.length - 2`.
- If `nums[i]` is the same as `nums[i-1]`, skip to the next iteration to avoid recounting plateaus.
- Find the left neighbor: Search backwards from `i-1` to find the first element `leftVal` not equal to `nums[i]`.
- Find the right neighbor: Search forwards from `i+1` to find the first element `rightVal` not equal to `nums[i]`.
- If both `leftVal` and `rightVal` neighbors exist:
  - Check if `(nums[i] > leftVal && nums[i] > rightVal)` or `(nums[i] < leftVal && nums[i] < rightVal)`.
  - If the condition is true, increment `count`.
- Return `count`.

## Pre-processing with Extra Space
A more efficient approach is to first simplify the array by removing consecutive duplicates. This transforms plateaus into single points, making the identification of hills and valleys straightforward.
**Time:** O(N) because we iterate through the original array once to build the new list and then iterate through the new list (at most `N` elements) once. · **Space:** O(N) in the worst case, as the new list could potentially store all elements if there are no consecutive duplicates.
**Pros:** Much faster than the brute-force approach with a linear time complexity.; The logic is clean and easy to follow once the array is simplified.
**Cons:** Requires extra space proportional to the number of elements in the worst case.
### Explanation
The core idea is that a plateau like `[2, 4, 4, 4, 1]` behaves like a single peak `[2, 4, 1]`. By removing consecutive duplicates, we can simplify the problem.
First, we create a new list. We iterate through the input `nums` and add an element to our new list only if it's different from the last element added. This effectively filters out all plateaus.
After this pre-processing step, we have a new array where no two adjacent elements are the same.
Then, we can simply iterate through this new array from its second element to its second-to-last element. For each element `A[i]`, we check if it's a hill (`A[i-1] < A[i] > A[i+1]`) or a valley (`A[i-1] > A[i] < A[i+1]`).

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int countHillValley(int[] nums) {
        // Step 1: Remove consecutive duplicates
        List<Integer> distinctNums = new ArrayList<>();
        distinctNums.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                distinctNums.add(nums[i]);
            }
        }

        // Step 2: Count hills and valleys in the simplified list
        if (distinctNums.size() < 3) {
            return 0;
        }

        int count = 0;
        for (int i = 1; i < distinctNums.size() - 1; i++) {
            int left = distinctNums.get(i - 1);
            int middle = distinctNums.get(i);
            int right = distinctNums.get(i + 1);

            if (middle > left && middle > right) {
                count++; // Hill
            } else if (middle < left && middle < right) {
                count++; // Valley
            }
        }

        return count;
    }
}
```
### Algorithm
- Create a new `ArrayList<Integer>` called `distinctNums`.
- Add the first element `nums[0]` to `distinctNums`.
- Iterate through `nums` from the second element. If `nums[i]` is not equal to the last element in `distinctNums`, add `nums[i]`.
- If the size of `distinctNums` is less than 3, return 0.
- Initialize `count = 0`.
- Iterate `i` from 1 to `distinctNums.size() - 2`.
- Check if `distinctNums.get(i)` is a hill or valley compared to its neighbors `distinctNums.get(i-1)` and `distinctNums.get(i+1)`.
- If it is, increment `count`.
- Return `count`.

## Optimal Single Pass with Constant Space
This is the most optimal approach. It achieves linear time complexity without using any extra space. It works by iterating through the array and identifying triplets of consecutive, distinct elements to check for hills or valleys.
**Time:** O(N). Although there's a nested `while` loop, each element in the array is visited a constant number of times by pointers `i` and `j` combined. The total work is proportional to `N`. · **Space:** O(1). We only use a few variables to store the count and the `left` value.
**Pros:** Most efficient solution in both time and space.; Processes the array in a single pass without modification or extra data structures.
**Cons:** The logic with multiple pointers can be slightly more complex to reason about compared to the pre-processing approach.
### Explanation
This method simulates the logic of the pre-processing approach but does it in-place, thus avoiding the `O(N)` space overhead.
We use a variable `left` to keep track of the value of the previous distinct element. We iterate through the array with a main pointer `i`.
We start iterating from `i = 1`. For each `nums[i]`, we compare it with the `left` value.
If `nums[i]` is the same as `left`, it's part of a plateau, and we continue.
If `nums[i]` is different from `left`, it's a potential peak or trough. We then need to find the next distinct element to its right. We use a second pointer `j` starting from `i + 1` to find the first `nums[j]` that is different from `nums[i]`.
If such a `right` element `nums[j]` exists, we have a triplet of distinct values: `(left, nums[i], nums[j])`. We can then apply the hill/valley check.
After checking, we update `left` to `nums[i]` and continue the main iteration.

```java
class Solution {
    public int countHillValley(int[] nums) {
        int count = 0;
        int left = nums[0];

        for (int i = 1; i < nums.length - 1; i++) {
            // Find the right neighbor, skipping plateaus
            int right = nums[i + 1];
            if (nums[i] == right) {
                // If current element is part of a plateau, find the end of it
                int j = i + 1;
                while (j < nums.length - 1 && nums[j] == nums[i]) {
                    j++;
                }
                right = nums[j];
                // Move i to the end of the plateau to avoid redundant checks
                i = j - 1;
            }

            // Check for hill or valley
            if (nums[i] > left && nums[i] > right) {
                count++;
            } else if (nums[i] < left && nums[i] < right) {
                count++;
            }
            
            // Update left to the current value for the next iteration
            left = nums[i];
        }

        return count;
    }
}
```
### Algorithm
- Initialize `count = 0` and `left = nums[0]`.
- Loop `i` from 1 to `nums.length - 1`.
- If `nums[i]` is equal to `left`, we are on a plateau. Continue to the next `i`.
- If `nums[i]` is different, it's a potential peak/trough. We need to find its right neighbor.
- Search for the right neighbor: Start a pointer `j` from `i + 1`. While `j < nums.length` and `nums[j] == nums[i]`, increment `j`.
- If `j` reaches the end of the array, it means `nums[i]` has no right non-equal neighbor, so we can stop.
- If `j` is a valid index, we have our triplet: `left`, `nums[i]`, and `nums[j]`.
- Check if `nums[i]` is a hill (`nums[i] > left && nums[i] > nums[j]`) or a valley (`nums[i] < left && nums[i] < nums[j]`).
- If it is, increment `count`.
- Update `left = nums[i]` to prepare for the next distinct element.
- The main loop continues from the next `i`.

# Solutions
### Java

```java
class Solution {
public
  int countHillValley(int[] nums) {
    int ans = 0;
    for (int i = 1, j = 0; i < nums.length - 1; ++i) {
      if (nums[i] == nums[i + 1]) {
        continue;
      }
      if (nums[i] > nums[j] && nums[i] > nums[i + 1]) {
        ++ans;
      }
      if (nums[i] < nums[j] && nums[i] < nums[i + 1]) {
        ++ans;
      }
      j = i;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countHillValley(vector<int> &nums) {
    int ans = 0;
    for (int i = 1, j = 0; i < nums.size() - 1; ++i) {
      if (nums[i] == nums[i + 1])
        continue;
      if (nums[i] > nums[j] && nums[i] > nums[i + 1])
        ++ans;
      if (nums[i] < nums[j] && nums[i] < nums[i + 1])
        ++ans;
      j = i;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countHillValley(self, nums: List[int]) -> int: arr = [nums[0]] for v in nums[1:]: if v != arr[- 1]: arr . append(v) return sum((arr[i] < arr[i - 1]) == (arr[i] < arr[i + 1]) for i in range(1, len(arr) - 1))

```