Problem Description

You are given a 0-indexed integer array nums. The problem asks you to identify and count hills and valleys in the array.

A hill is defined as an index i where:

• The element at index i is greater than both its closest non-equal neighbors
• It must have non-equal neighbors on both left and right sides

A valley is defined as an index i where:

• The element at index i is smaller than both its closest non-equal neighbors
• It must have non-equal neighbors on both left and right sides

Key points to understand:

• Closest non-equal neighbors: When looking for neighbors, skip over any adjacent elements that have the same value as nums[i]
• Adjacent equal elements: If nums[i] == nums[j] for adjacent indices i and j, they are considered part of the same hill or valley
• Boundary elements: Elements at the start or end of the array cannot be hills or valleys since they don't have neighbors on both sides

For example, in the array [2, 4, 1, 1, 6, 5]:

• Index 1 (value 4) is a hill because 4 > 2 (left neighbor) and 4 > 1 (right neighbor)
• Indices 2 and 3 (both value 1) form a valley together because 1 < 4 (left neighbor) and 1 < 6 (right neighbor)
• Index 4 (value 6) is a hill because 6 > 1 (left neighbor) and 6 > 5 (right neighbor)

The task is to return the total count of hills and valleys in the given array.

Intuition

The key insight is that we need to handle consecutive equal elements carefully. When we have equal adjacent elements like [3, 3, 3], they all belong to the same hill or valley and should be counted as one unit, not multiple.

To solve this, we can think of "compressing" consecutive equal elements into a single representative element. Instead of checking every element against its neighbors, we only need to check positions where the value changes.

The approach uses two pointers:

• Pointer i traverses through the array normally
• Pointer j keeps track of the last position where we found a different value

Here's the thought process:

1. Skip consecutive duplicates: When nums[i] == nums[i+1], we skip because these elements belong to the same hill/valley group.

2. Compare with the last different element: Instead of looking backward through potentially many equal elements to find the left neighbor, we maintain pointer j that remembers where the last different value was. This gives us the "closest non-equal left neighbor."

3. Check for hill or valley: At position i (when it's different from i+1), we check:

   • Is it a hill? nums[i] > nums[j] (greater than left) AND nums[i] > nums[i+1] (greater than right)
   • Is it a valley? nums[i] < nums[j] (less than left) AND nums[i] < nums[i+1] (less than right)

4. Update the reference point: After checking, we update j = i because i now becomes the new reference point for the next comparison.

This way, we efficiently handle consecutive equal elements and correctly identify each distinct hill and valley in the array.

Solution Approach

The implementation follows a single-pass traversal approach with two pointers to efficiently identify hills and valleys:

Algorithm Steps:

1. Initialize variables:

   • ans = 0 to count the total number of hills and valleys
   • j = 0 to track the position of the last different element (our left reference point)

2. Traverse the array from index 1 to len(nums) - 1:

   • We start from index 1 and end at len(nums) - 1 because hills and valleys need neighbors on both sides

3. Handle consecutive equal elements:

   • If nums[i] == nums[i + 1], we skip the current iteration with continue
   • This ensures we only process positions where the value changes

4. Check for hill:

   • If nums[i] > nums[j] (greater than left neighbor) AND nums[i] > nums[i + 1] (greater than right neighbor)
   • Increment ans by 1

5. Check for valley:

   • If nums[i] < nums[j] (less than left neighbor) AND nums[i] < nums[i + 1] (less than right neighbor)
   • Increment ans by 1

6. Update the reference pointer:

   • Set j = i to make the current position the new reference for future comparisons
   • This happens after checking for hills/valleys

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

• i=1: nums[1]=4, nums[0]=2, nums[2]=1 → Hill detected (4 > 2 and 4 > 1), ans=1, j=1
• i=2: nums[2]=1, nums[3]=1 → Skip (equal values)
• i=3: nums[3]=1, nums[1]=4, nums[4]=6 → Valley detected (1 < 4 and 1 < 6), ans=2, j=3
• i=4: nums[4]=6, nums[3]=1, nums[5]=5 → Hill detected (6 > 1 and 6 > 5), ans=3, j=4

Time Complexity: O(n) - single pass through the array
Space Complexity: O(1) - only using a few variables

Example Walkthrough

Let's walk through the solution with nums = [6, 6, 5, 5, 4, 1]:

Initial Setup:

• ans = 0 (count of hills and valleys)
• j = 0 (tracks last different element position)

Step 1: i = 1

• Current: nums[1] = 6
• Next: nums[2] = 5
• Since nums[1] ≠ nums[2], we proceed to check
• Left neighbor: nums[j] = nums[0] = 6
• Right neighbor: nums[2] = 5
• Check hill: Is 6 > 6 AND 6 > 5? No (6 is not greater than 6)
• Check valley: Is 6 < 6 AND 6 < 5? No
• No hill or valley found
• Update: j = 1

Step 2: i = 2

• Current: nums[2] = 5
• Next: nums[3] = 5
• Since nums[2] == nums[3], skip this iteration (consecutive equal elements)

Step 3: i = 3

• Current: nums[3] = 5
• Next: nums[4] = 4
• Since nums[3] ≠ nums[4], we proceed to check
• Left neighbor: nums[j] = nums[1] = 6
• Right neighbor: nums[4] = 4
• Check hill: Is 5 > 6 AND 5 > 4? No
• Check valley: Is 5 < 6 AND 5 < 4? No (5 is less than 6 but not less than 4)
• No hill or valley found
• Update: j = 3

Step 4: i = 4

• Current: nums[4] = 4
• Next: nums[5] = 1
• Since nums[4] ≠ nums[5], we proceed to check
• Left neighbor: nums[j] = nums[3] = 5
• Right neighbor: nums[5] = 1
• Check hill: Is 4 > 5 AND 4 > 1? No
• Check valley: Is 4 < 5 AND 4 < 1? No (4 is less than 5 but not less than 1)
• No hill or valley found
• Update: j = 4

Result: ans = 0 (no hills or valleys found)

This example demonstrates how the algorithm:

1. Skips consecutive equal elements (indices 2 and 3 both have value 5)
2. Uses pointer j to track the last different value for left neighbor comparison
3. Only counts an element as a hill/valley when it's strictly greater/less than BOTH neighbors

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array once with a single for loop from index 1 to len(nums) - 1, performing constant-time operations (comparisons and variable assignments) at each iteration.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space for variables ans, j, and i, regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Handling Consecutive Equal Elements

The Problem: A common mistake is treating each equal element as a separate potential hill or valley. For example, in [1, 2, 2, 2, 1], developers might incorrectly count multiple hills at indices 1, 2, and 3, when actually all three positions with value 2 form a single hill.

Why It Happens: The intuitive approach of checking each index against its immediate neighbors fails when consecutive elements are equal:

# INCORRECT approach
for i in range(1, len(nums) - 1):
    if nums[i] > nums[i-1] and nums[i] > nums[i+1]:
        count += 1

The Solution: Skip processing when the current element equals the next element, and maintain a reference to the last different element:

if nums[i] == nums[i + 1]:
    continue  # Skip to avoid double-counting

Pitfall 2: Using Immediate Neighbors Instead of Closest Non-Equal Neighbors

The Problem: Another mistake is comparing with immediate neighbors (i-1 and i+1) rather than the closest non-equal neighbors. In [6, 6, 5, 5, 4, 1], index 2 (value 5) should be compared with value 6 on the left and value 1 on the right, not with another 5.

Why It Happens: The problem statement's requirement for "closest non-equal neighbors" can be misunderstood:

# INCORRECT: Always using i-1 as left neighbor
if nums[i] < nums[i-1] and nums[i] < nums[i+1]:
    count += 1

The Solution: Maintain a pointer prev_different_idx that tracks the last position where the value was different:

# After checking for hills/valleys
prev_different_idx = i  # Update reference point

Pitfall 3: Forgetting to Update the Reference Pointer

The Problem: Failing to update prev_different_idx after each iteration leads to incorrect comparisons. The left neighbor reference becomes stale and doesn't represent the actual closest non-equal neighbor.

Why It Happens: Developers might update the pointer only when a hill or valley is found, missing updates for "flat" transitions:

# INCORRECT: Only updating when hill/valley found
if (hill or valley condition):
    count += 1
    prev_different_idx = i  # Wrong placement

The Solution: Always update prev_different_idx after processing each distinct element, regardless of whether it's a hill or valley:

# Process current element
if nums[i] > nums[prev_different_idx] and nums[i] > nums[i + 1]:
    count += 1
# ... valley check ...

# ALWAYS update the reference pointer
prev_different_idx = i