Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Equal adjacent values form one plateau and must be judged together. A plateau is a hill when its nearest different neighbors on both sides are lower, or a valley when both are higher. Boundary plateaus lacking either neighbor do not count.

Approach

Scan from the second position, advancing a right pointer past all equal values of the current plateau. If it reaches the array end, stop. Compare the plateau value with the previous position and the first different value on the right, counting one strict local maximum or minimum. Jump directly to that right position for the next iteration. An initial equal-valued plateau fails the strict left comparison, correctly excluding it.

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

        while i < n - 1:
            l = i - 1
            r = i + 1
            while r < n and nums[r] == nums[i]:
                r += 1
            if r == n:
                break
            hill = nums[l] < nums[i] and nums[r] < nums[i]
            valley = nums[l] > nums[i] and nums[r] > nums[i]
            if hill or valley:
                res += 1
            i = r

        return res

Complexity analysis

Let n = nums.length. Time: O(n), because the scan skips each plateau once. Auxiliary space: O(1).