Count Hills and Valleys in an Array

EASY

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.

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

Checkout 3 different approaches to solve Count Hills and Valleys in an Array. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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]).

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

Complexity Analysis

Time Complexity: 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 Complexity: O(N) in the worst case, as the new list could potentially store all elements if there are no consecutive duplicates.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Count Hills and Valleys in an Array. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Count Hills and Valleys in an Array

Data Structures:

Array