Count Hills And Valleys In An Array - Leetcode Solution

Problem Statement:

Given an array of integers, count the number of hills and valleys in the array.

A hill is any sequence of adjacent elements in the array that starts with an element less than the next element, and ends with an element greater than the last element.

A valley is the opposite - any sequence of adjacent elements in the array that starts with an element greater than the next element, and ends with an element less than the last element.

Example:

Input: [1,2,3,2,1,2,1]

Output: 2

Explanation: The array has two hills (3-2-1 and 2-1) and one valley (1-2-3).

Solution:

We can approach this problem by iterating over the array, and keeping track of the current trend (upwards or downwards). We can start by defining two variables: prev, which stores the previous element in the array, and trend, which stores the current trend.

Initially, prev is set to the first element in the array, and trend is set to 0 (i.e., we have not started a hill or valley yet).

We then iterate over the remaining elements in the array, and compare each element with the previous element (prev). If the current element is greater than the previous element, and the current trend is downwards (i.e., we just finished a valley), we increment the count of hills and start a new hill.

If the current element is less than the previous element, and the current trend is upwards (i.e., we just finished a hill), we increment the count of valleys and start a new valley.

At the end of each iteration, we update the value of prev to be the current element, and the value of trend to reflect the current trend (i.e., 1 if the current element is greater than the previous element, and -1 if it is less than the previous element).

Here's the implementation of this approach:

def count_hills_and_valleys(arr):
    n = len(arr)
    if n <= 1:
        return 0
    
    prev = arr[0]
    trend = 0
    
    hills = valleys = 0
    
    for i in range(1, n):
        if arr[i] > prev:
            if trend == -1:
                hills += 1
                trend = 1
        elif arr[i] < prev:
            if trend == 1:
                valleys += 1
                trend = -1
        
        prev = arr[i]
    
    return hills + valleys

We start by checking if the array has less than 2 elements, in which case we cannot have any hills or valleys.

We then initialize prev to the first element in the array, and trend to 0.

We iterate over the remaining elements in the array, and check if the current element is greater than or less than the previous element. If the current trend is downwards and the current element is greater than the previous element, we increment hills and update trend to 1. If the current trend is upwards and the current element is less than the previous element, we increment valleys and update trend to -1.

At the end, we return the sum of hills and valleys.

Time Complexity: O(n), where n is the length of the input array. We need to iterate over the array once.

Space Complexity: O(1). We only need to store a few variables to keep track of the state of the iteration.

1