LeetCode 2210 - Count Hills and Valleys in an Array

The problem asks us to identify hills and valleys in an integer array nums. A hill is a position where the closest non-equal neighbors on both sides are smaller than the current value, and a valley is where those neighbors are larger.

leetcodeeasyarray

LeetCode Problem 2210

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem asks us to identify hills and valleys in an integer array nums. A hill is a position where the closest non-equal neighbors on both sides are smaller than the current value, and a valley is where those neighbors are larger. Consecutive elements with the same value are considered part of the same hill or valley, so duplicates should not be double-counted. The result is the total count of distinct hills and valleys.

The input nums is guaranteed to have a length of at least 3 and all values between 1 and 100. Because each element must have both left and right non-equal neighbors to qualify as a hill or valley, the first and last elements cannot be hills or valleys. Edge cases include consecutive duplicates and plateaus where multiple identical values are grouped together; these must be treated as a single hill or valley if the surrounding values allow.

The expected output is a single integer representing the number of hills and valleys in the array.

Approaches

A brute-force approach would examine each element, skip the first and last elements, and find the closest non-equal neighbors to check the hill or valley condition. While correct, this requires scanning left and right for each element, leading to a worst-case time complexity of O(n²), which is acceptable here due to the small constraints but unnecessary.

The optimal approach observes that we can first compress consecutive duplicates to reduce redundant checks. After compression, each remaining element can be compared with its immediate neighbors. This eliminates the need to scan left and right repeatedly. The approach is linear in time relative to the compressed array length, which is at most n.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Scan left and right for each element to find non-equal neighbors
Optimal O(n) O(n) Compress duplicates and compare neighbors directly

Algorithm Walkthrough

  1. Initialize an empty list compressed to store the sequence of distinct consecutive numbers.
  2. Iterate through nums. For each element, append it to compressed only if it is different from the previous element.
  3. Initialize a counter count to zero.
  4. Iterate through compressed from the second element to the second-to-last element.
  5. For each element, compare it with its immediate neighbors: if it is greater than both, increment count for a hill; if it is smaller than both, increment count for a valley.
  6. Return count.

Why it works: By compressing duplicates first, we ensure that plateaus are treated as a single unit. Comparing only immediate neighbors in the compressed array accurately reflects the closest non-equal neighbors in the original array. This guarantees correctness while avoiding redundant checks.

Python Solution

from typing import List

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        if not nums or len(nums) < 3:
            return 0

        # Step 1: compress consecutive duplicates
        compressed = [nums[0]]
        for num in nums[1:]:
            if num != compressed[-1]:
                compressed.append(num)

        count = 0
        # Step 2: check hills and valleys in compressed array
        for i in range(1, len(compressed) - 1):
            if compressed[i] > compressed[i-1] and compressed[i] > compressed[i+1]:
                count += 1
            elif compressed[i] < compressed[i-1] and compressed[i] < compressed[i+1]:
                count += 1

        return count

The Python solution first compresses consecutive duplicates to simplify neighbor comparison. Then, it iterates over the compressed array, checking if each element forms a hill or valley by comparing with its left and right neighbors. This eliminates false counts from plateaus.

Go Solution

func countHillValley(nums []int) int {
    if len(nums) < 3 {
        return 0
    }

    // Step 1: compress consecutive duplicates
    compressed := []int{nums[0]}
    for i := 1; i < len(nums); i++ {
        if nums[i] != compressed[len(compressed)-1] {
            compressed = append(compressed, nums[i])
        }
    }

    count := 0
    // Step 2: check hills and valleys in compressed array
    for i := 1; i < len(compressed)-1; i++ {
        if compressed[i] > compressed[i-1] && compressed[i] > compressed[i+1] {
            count++
        } else if compressed[i] < compressed[i-1] && compressed[i] < compressed[i+1] {
            count++
        }
    }

    return count
}

The Go solution mirrors the Python logic. The slice compressed handles duplicate compression, and iteration checks immediate neighbors for hills and valleys. Go-specific considerations include dynamic slice appends and explicit length checks.

Worked Examples

Example 1: nums = [2,4,1,1,6,5]

Compress duplicates: [2,4,1,6,5]

Iteration steps:

i Value Left Right Hill/Valley Count
1 4 2 1 Hill 1
2 1 4 6 Valley 2
3 6 1 5 Hill 3

Return 3.

Example 2: nums = [6,6,5,5,4,1]

Compress duplicates: [6,5,4,1]

Iteration steps:

i Value Left Right Hill/Valley Count
1 5 6 4 Neither 0
2 4 5 1 Neither 0

Return 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Compressing duplicates and scanning neighbors each require O(n) time.
Space O(n) Compressed array can be at most length n, storing it requires O(n) space.

The time complexity is linear because each element is processed at most twice: once during compression and once during neighbor comparison. The space complexity is linear due to the compressed array.

Test Cases

# Provided examples
assert Solution().countHillValley([2,4,1,1,6,5]) == 3  # multiple hills/valleys
assert Solution().countHillValley([6,6,5,5,4,1]) == 0  # no hills/valleys

# Edge cases
assert Solution().countHillValley([1,2,3]) == 0  # strictly increasing
assert Solution().countHillValley([3,2,1]) == 0  # strictly decreasing
assert Solution().countHillValley([1,2,2,1]) == 1  # plateau forms hill
assert Solution().countHillValley([1,1,1,1]) == 0  # all equal
assert Solution().countHillValley([1,3,3,3,2,4,4,3]) == 3  # multiple plateaus with hills/valleys
Test Why
[2,4,1,1,6,5] Multiple hills and valleys with duplicates
[6,6,5,5,4,1] No hills or valleys
[1,2,3] Strictly increasing array
[3,2,1] Strictly decreasing array
[1,2,2,1] Plateau forms a hill
[1,1,1,1] All equal elements, no hills/valleys
[1,3,3,3,2,4,4,3] Complex plateaus with multiple hills and valleys

Edge Cases

  1. Strictly increasing or decreasing arrays: In such arrays, no element can be a hill or valley because at least one neighbor will always be larger or smaller, respectively. Our solution correctly returns zero because the neighbor comparison never succeeds.
  2. Plateaus at the start or end: If duplicates occur at the beginning or end of the array, they cannot be hills or valleys since one side lacks a neighbor. Compression ensures duplicates do not cause incorrect counts.
  3. Multiple consecutive duplicates in the middle: Long plateaus can either form a hill, a valley, or neither. By compressing duplicates first, all identical consecutive values are treated as a single element. Neighbor comparison then correctly identifies if the plateau constitutes a hill or valley, avoiding double-counting.