We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Hills and Valleys in an Array

Number: 2316

Difficulty: Easy

Paid? No

Companies: Meta, Microsoft

Problem Description

Given an array of integers, the task is to count the number of hills and valleys in the array. An index is considered part of a hill if its closest non-equal left and right neighbors are both less than the element at that index. Similarly, an index is part of a valley if its closest non-equal left and right neighbors are both greater than it. Consecutive indices with equal values form one hill or valley group. Note that an index must have non-equal neighbors on both sides to be counted as either.

Key Insights

  • Removing consecutive duplicates simplifies the problem because repeated elements belong to the same hill or valley.
  • After deduplication, only indices with both a left and right neighbor need to be evaluated.
  • For each candidate index, compare it with its immediate neighbors to decide if it forms a hill (greater than both neighbors) or a valley (less than both neighbors).

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input array, due to the linear scan for deduplication and evaluation. Space Complexity: O(n) in the worst case, for storing the deduplicated array.

Solution

The solution first deduplicates the input array to collapse contiguous groups of equal numbers into one representative element. This is important because multiple adjacent equal elements should only count as one potential hill or valley.

Next, we traverse the deduplicated list starting from the second element and ending at the second-to-last element to ensure that each element considered has both a left and right neighbor. For each such element, we compare it with its immediate neighbors:

  • If the element is greater than both neighbors, it is part of a hill.
  • If it is less than both neighbors, it is part of a valley.

Finally, we count the number of hills and valleys found.

Code Solutions

# Python solution for counting hills and valleys in an array

def count_hills_valleys(nums):
    # Step 1: Deduplicate the array by collapsing consecutive equal elements.
    deduped = [nums[0]]
    for num in nums[1:]:
        if num != deduped[-1]:
            deduped.append(num)
    
    count = 0
    # Step 2: Iterate over the deduped array, skipping the first and last elements.
    for i in range(1, len(deduped) - 1):
        # Check if the current element is greater than both neighbors (hill)
        if deduped[i] > deduped[i - 1] and deduped[i] > deduped[i + 1]:
            count += 1
        # Check if the current element is less than both neighbors (valley)
        elif deduped[i] < deduped[i - 1] and deduped[i] < deduped[i + 1]:
            count += 1
    return count

# Example usage:
example_nums = [2,4,1,1,6,5]
print(count_hills_valleys(example_nums)) # Expected output: 3
← Back to All Questions