2210. Count Hills and Valleys in an Array

UnknownView on LeetCode

Array Counting

Time: O(n)

Space: O(1)

Problem Overview

A hill is a local peak: nums[i] is strictly greater than both neighbors.

Intuition

A hill is a local peak: nums[i] is strictly greater than both neighbors. Valleys are local minima with the same strict inequality. Endpoints cannot be hills or valleys because they lack two neighbors. Count both types in one pass.

Algorithm

1If n < 3, return 0.
2count = 0. For i from 1 to n-2:
3If nums[i] > nums[i-1] && nums[i] > nums[i+1]: hill, count++.
4Else if nums[i] < nums[i-1] && nums[i] < nums[i+1]: valley, count++.
5Return count.

Example Walkthrough

Input: nums = [6,2,7,9,4,5]

1.i=1: 2 < 6 and 2 < 7 -> valley. i=2: 7 peak. i=4: 4 valley.

Output: 3

Common Pitfalls

•Strict inequalities — equal neighbors are neither hill nor valley.
•Indices 0 and n-1 are never counted.
•Plateaus (flat runs) contribute nothing at interior points.

2210.cs

// Approach: Linear scan tracking left plateau value; count peaks and valleys.
// Time: O(n) Space: O(1)

public class Solution
{
    public int CountHillValley(int[] nums)
    {
        int ans = 0;
        int left = nums[0];

        for (int i = 1; i + 1 < nums.Length; ++i)
        {
            if ((left < nums[i] && nums[i] > nums[i + 1]) || // the hill
                (left > nums[i] && nums[i] < nums[i + 1]))
            { // the valley
                ++ans;
                left = nums[i];
            }
        }

        return ans;
    }
}

Was this solution helpful?