2210. Count Hills and Valleys in an Array

Problem Statement

link: LeetCode.cn LeetCode You are given a 0-indexed integer array nums. An index i is part of a hill in nums if the closest non-equal neighbors of i are smaller than nums[i]. Similarly, an index i is part of a valley in nums if the closest non-equal neighbors of i are larger than nums[i]. Adjacent indices i and j are part of the same hill or valley if nums[i] == nums[j].

Note that for an index to be part of a hill or valley, it must have a non-equal neighbor on both the left and right of the index.

Return the number of hills and valleys in nums.

Example:

Input: nums = [2,4,1,1,6,5] Output: 3

Input: nums = [6,6,5,5,4,1] Output: 0

Input: nums = [1,2], k = 0 Output: 1

Constraints: 3 <= nums.length <= 100 1 <= nums[i] <= 100

Solution Approach

The solution iterates through the array, skipping equal adjacent values, and checks if each element forms a hill or valley by comparing it to its nearest non-equal neighbors, then counts the valid hills and valleys.

Algorithm

1. Skip Equal Adjacent Values: The algorithm skips consecutive equal elements to avoid redundant checks and focus on potential hill or valley points.
2. Compare Neighbors: For each potential hill or valley, the algorithm compares it to its nearest non-equal neighbors on both sides to determine if it’s a hill (greater than both neighbors) or a valley (less than both neighbors).
3. Count Valid Hills and Valleys: The algorithm counts each index that satisfies the hill or valley conditions and returns the total count.

   Complexity

   time complexity: O(n^2) space complexity: O(1)

Implement

    class Solution:
     def countHillValley(self, nums: List[int]) -> int:
         res = 0
         n = len(nums)
         for i in range(1, n - 1):
             if nums[i] == nums[i - 1]:
                 continue
             left = 0
             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
             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:
                 res += 1
         return res

    
    

Twitter  facebook  Email