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
