Problem of The Day: Count Hills and Valleys in an Array

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        res = 0
        indices = set()
        for i in range(1, len(nums) - 1):
            if i in indices:
                continue
            l, r = i - 1, i + 1
            while l > 0 and nums[l] == nums[i]:
                l -= 1
            while r < len(nums) - 1 and nums[r] == nums[i]:
                r += 1
            if (nums[i] > nums[l] and nums[i] > nums[r]) or \
                (nums[i] < nums[l] and nums[i] < nums[r]):
                indices.update(range(l, r))
                res += 1
        return res

Editorial

Approach: Count the Number of Peaks and Valleys in the Array

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        res = 0  # number of peaks and valleys
        n = len(nums)
        for i in range(1, n - 1):
            if nums[i] == nums[i - 1]:
                # deduplication
                continue
            left = (
                0  # left side possibly unequal neighboring corresponding state
            )
            for j in range(i - 1, -1, -1):
                if nums[j] > nums[i]:
                    left = 1
                    break
                elif nums[j] < nums[i]:
                    left = -1
                    break
            right = (
                0  # right side possibly unequal neighboring corresponding state
            )
            for j in range(i + 1, n):
                if nums[j] > nums[i]:
                    right = 1
                    break
                elif nums[j] < nums[i]:
                    right = -1
                    break
            if left == right and left != 0:
                # at this time, index i is part of a peak or valley.
                res += 1
        return res