Count Hills and Valleys in an Array - Practice Coding Problems

Count Hills and Valleys in an Array - Problem

Array Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,1,3,2,4,1]

› Output: 3

💡 Note: Index 1 is valley (2 > 1 < 3), index 3 is valley (3 > 2 < 4), index 5 is valley (4 > 1, no right neighbor so not counted). Actually index 1, 3, and 4 form hills/valleys, so answer is 3.

Example 2 — Equal Adjacent Values

$ Input: nums = [6,6,5,5,4,1]

› Output: 0

💡 Note: No hills or valleys exist. Adjacent equal values like 6,6 and 5,5 are treated as same elevation level.

Example 3 — Single Hill

$ Input: nums = [1,4,1]

› Output: 1

💡 Note: Index 1 forms a hill since both neighbors (1,1) are smaller than 4.

Constraints

3 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with values representing elevation points

Find Patterns

Identify hills (higher than neighbors) and valleys (lower than neighbors)

Count Result

Return total number of hills and valleys found

Key Takeaway

🎯 Key Insight: Adjacent equal values belong to the same hill or valley, so we only need to compare with the nearest different neighbors

Asked in

G Google 15 a Amazon 12 f Meta 8

The key insight is that adjacent equal values belong to the same hill or valley. Best approach uses single pass tracking the previous different value to avoid redundant scanning. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Each Position	O(n²)	O(1)	For each position, find closest non-equal neighbors on both sides
One Pass with Previous Tracking	O(n)	O(1)	Single pass tracking the last different value seen

Brute Force - Check Each Position — Algorithm Steps

For each index i from 1 to n-2
Scan left to find closest non-equal neighbor
Scan right to find closest non-equal neighbor
Check if i forms hill or valley
Count total hills and valleys

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Position

For each index, find closest different values

Compare Neighbors

Check if both neighbors are smaller (hill) or larger (valley)

Count Result

Increment counter for each hill or valley found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    if (n < 3) return 0;
    
    int count = 0;
    
    for (int i = 1; i < n - 1; i++) {
        // Find left neighbor (closest non-equal)
        int left = i - 1;
        while (left >= 0 && nums[left] == nums[i]) {
            left--;
        }
        
        // Find right neighbor (closest non-equal)
        int right = i + 1;
        while (right < n && nums[right] == nums[i]) {
            right++;
        }
        
        // Check if we have valid neighbors on both sides
        if (left >= 0 && right < n) {
            // Check if it's a hill or valley
            if ((nums[left] < nums[i] && nums[right] < nums[i]) ||
                (nums[left] > nums[i] && nums[right] > nums[i])) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each position, we may scan up to n positions left and right

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

18.0K Views

Medium Frequency

~15 min Avg. Time

430 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Each Position — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler