Problem Statement in English

You’re given an array of integers nums. A hill is defined as a position i where nums[i-1] < nums[i] > nums[i+1], and a valley is defined as a position i where nums[i-1] > nums[i] < nums[i+1]. Your task is to count the number of hills and valleys in the array.

Approach

To solve this problem, we can use a stack to keep track of the unique elements in the array while maintaining their relative order. This will help us identify the hills and valleys more easily.

  1. Remove Consecutive Duplicates: First, we need to remove consecutive duplicates from the array. This is because hills and valleys are only defined between different numbers. We can use a stack to achieve this.

  2. Count Hills and Valleys: Once we have a cleaned-up version of the array (with no consecutive duplicates), we can iterate through it and count the hills and valleys based on the definitions provided.

Solution in Python


class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        stack = []
        for n in nums:
            if stack and stack[-1] != n:
                stack.append(n)
            elif not stack:
                stack.append(n)

        if len(stack) <= 2:
            return 0

        res = 0

        for r in range(1, len(stack) - 1):
            if stack[r - 1] > stack[r] < stack[r + 1]:
                res += 1
            elif stack[r - 1] < stack[r] > stack[r + 1]:
                res += 1

        return res

Complexity

  • Time: O(n)O(n)
    Since we iterate through the array twice: once to remove duplicates and once to count hills and valleys.

  • Space: O(n)O(n)
    The space complexity is O(n)O(n) due to the stack used to store unique consecutive elements.

And we are done.