Count Hills and Valleys in an Array

Easy

Count Hills and Valleys in an Array

Easy

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array contain duplicate values, and if so, how should they be handled when determining if a point is a hill or valley?
What is the expected return value if the input array is null or empty?
Are the numbers in the input array integers? What is the range of possible values for each number?
For an element to be considered a hill or valley, does it need to be strictly greater/less than its neighbors, or is greater/less than or equal to sufficient?
If the first or last element is a hill or valley, how do you define its neighbors (e.g., treat them as negative infinity, positive infinity, or ignore them)?

Brute Force Solution

Approach

Imagine you're looking at a landscape made of blocks, some taller and some shorter. To find the hills and valleys the most straightforward way is to look at each block one by one and compare it to its neighbors.

Here's how the algorithm would work step-by-step:

Start by looking at the second block in the landscape.
Check if this block is taller than both the block before it and the block after it. If it is, then it's a hill, so count it.
If the block is not a hill, check if it's shorter than both the block before it and the block after it. If it is, then it's a valley, so count it.
If it's neither a hill nor a valley, then it's just a slope, so don't count it.
Move to the next block in the landscape and repeat the process.
Continue doing this until you have checked every block except the very first and very last block (as these cannot be hills or valleys).
The total number of hills and valleys you counted is the answer.

Code Implementation

def count_hills_and_valleys_brute_force(blocks):
    number_of_hills_and_valleys = 0
    # We skip the first and last elements.
    for index in range(1, len(blocks) - 1):

        # Compare current block with its neighbors
        previous_block = blocks[index - 1]
        current_block = blocks[index]
        next_block = blocks[index + 1]

        # Check for hill condition
        if current_block > previous_block and current_block > next_block:
            number_of_hills_and_valleys += 1

        # Check for valley condition
        elif current_block < previous_block and current_block < next_block:
            number_of_hills_and_valleys += 1

    return number_of_hills_and_valleys

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n, examining each element except the first and last. For each element, it performs a constant number of comparisons (two comparisons) to determine if it's a hill or a valley. Therefore, the number of operations is directly proportional to the size of the input array, resulting in a linear time complexity. The total operations can be approximated as examining (n-2) elements, each with a constant time comparison, which simplifies to O(n).

Space Complexity

O(1) – The algorithm iterates through the input array, but the plain English explanation does not mention creating any new data structures or storing any intermediate results besides the counters for hills and valleys. The operations only involve comparing elements in place and incrementing counters. Thus, the auxiliary space used is constant, independent of the input size N (the size of the array).

Optimal Solution

Approach

To efficiently count hills and valleys, we only need to compare each number to its neighbors. The key is to ignore flat plateaus and treat them as part of either a hill or a valley depending on the surrounding numbers.

Here's how the algorithm would work step-by-step:

Go through the list of numbers, one by one.
For each number, look at the numbers to its left and right.
If a number is bigger than both its neighbors, or if it is smaller than both its neighbors, mark it as a possible hill or valley.
If a number is equal to one or both of its neighbors, extend the 'flat' area to include these equal neighbors.
Keep expanding the 'flat' area until you reach a number that's different.
Compare the number at the end of the flat area to the numbers before the flat area, and that determines the hill or valley
Count the number of hills and valleys found by using this 'smart check' strategy.

Code Implementation

def count_hills_and_valleys(numbers):
    number_of_hills_and_valleys = 0
    length_of_numbers = len(numbers)

    for i in range(1, length_of_numbers - 1):
        left_index = i - 1
        right_index = i + 1

        # Find the closest different number on the left
        while left_index >= 0 and numbers[left_index] == numbers[i]:
            left_index -= 1

        # Find the closest different number on the right
        while right_index < length_of_numbers and numbers[right_index] == numbers[i]:
            right_index += 1

        # If either boundary goes out of range, it's not a hill/valley
        if left_index < 0 or right_index >= length_of_numbers:
            continue

        #Determine if current number is hill or valley
        if numbers[i] > numbers[left_index] and numbers[i] > numbers[right_index]:
            number_of_hills_and_valleys += 1

        if numbers[i] < numbers[left_index] and numbers[i] < numbers[right_index]:
            number_of_hills_and_valleys += 1

    return number_of_hills_and_valleys

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array once. For each element, it may extend a 'flat' area, but this extension only involves traversing elements adjacent to the current element and equal to it. Each element is visited and potentially extended from at most once during the main iteration. Therefore, the number of operations is directly proportional to the number of elements, n, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The provided plain English explanation describes an iterative process that primarily involves comparisons and updates of a few variables. It does not suggest the creation of any auxiliary data structures like lists, maps, or sets. The algorithm appears to use a constant number of variables to keep track of indices and comparisons, independent of the input array's size, N. Therefore, the auxiliary space complexity is O(1), indicating constant space.

Edge Cases

Case	How to Handle
Empty or null input array	Return 0, as there are no hills or valleys in an empty array.
Array with fewer than 3 elements	Return 0, as a hill or valley requires a peak/trough surrounded by two neighbors.
Array with all identical values	Return 0, because no element strictly satisfies the hill/valley condition when all neighbors are equal.
Consecutive duplicate values	Skip over consecutive duplicate values to find the next distinct neighbor for comparison.
Integer overflow during calculations if values are extremely large	Ensure to use appropriate data types (e.g., long) to prevent overflow during comparison.
Alternating high and low values (e.g., sawtooth pattern)	The algorithm should correctly identify each peak and trough as a hill or valley, respectively.
Input array containing negative numbers and/or zero	The comparison logic should work correctly regardless of whether the numbers are positive, negative, or zero.
Very large array sizes exceeding available memory	Ensure algorithm complexity stays linear to prevent excessive memory allocation errors.