2210. Count Hills and Valleys in an Array

EasyArray
Leetcode Link

Problem Description

In this problem, we are given an integer array nums which is 0-indexed. Our task is to determine how many hills and valleys the array contains. A hill is defined as an element which is larger than its closest distinctly different neighbors, and a valley is defined as an element which is smaller than its closest distinctly different neighbors. An important condition is that both neighbors must be different from the element being assessed and that equal elements adjacent to each other are considered as part of the same hill or valley.

Another important detail to consider is that an element needs to have distinct neighbors on both sides for it to be part of a hill or a valley. Hence, the first and the last elements of the array can never be hills or valleys since they lack a neighbor on one side.

Intuition

The intuition behind the solution is that, in order to find the hills and valleys, we should iterate through the array starting from the second element and ending at the second-to-last element. We compare each element with its neighbors to determine whether it forms a hill or a valley, taking into account that consecutive equal elements should be treated as one single entity.

The approach is to have two pointers, i and j, where i iterates through the array and j keeps track of the last element that is not equal to the current element i. By doing this, we skip over the equal elements because they don't help in determining a new hill or valley but are part of an existing one.

During each iteration, we compare nums[i] with nums[j] and nums[i+1]:

  • If nums[i] > nums[j] and nums[i] > nums[i+1], it means that nums[i] is a hill. We increment the answer counter.
  • If nums[i] < nums[j] and nums[i] < nums[i+1], it means that nums[i] is a valley. We increment the answer counter as well.
  • If nums[i] is equal to nums[i+1], we continue the iteration without changing j because we're still within the same hill or valley region.

Finally, after iterating through the array, the answer counter will contain the total number of hills and valleys in the array.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Solution Approach

The implementation of the solution provided is quite straightforward and does not use any complex data structures or algorithms. It relies on a single pass iteration with a simple comparison check. Let's walk through the key steps of the provided solution:

  1. Initialize two pointers i and j. i starts from 1 since the first element cannot be a hill or valley, and j starts from 0, which will keep track of the last index that has a different value from nums[i].
  2. Initialize a counter ans to 0 to keep track of the number of hills and valleys.
  3. Start a loop from the second element (index 1) to the second-to-last element (index len(nums) - 2, since we will be checking nums[i + 1]).
  4. Inside the loop:
    • If nums[i] == nums[i + 1], then skip the rest of the loop and continue with the next iteration as we're inside a range of duplicate elements that are part of the same hill or valley.
    • If nums[i] > nums[j] and nums[i] > nums[i + 1], we have found a hill, increment ans by 1.
    • If nums[i] < nums[j] and nums[i] < nums[i + 1], we have found a valley, increment ans by 1.
    • Update the j pointer to i as this comparison is complete, and i had a different value than nums[i + 1].
  5. After the loop ends, return the value of ans, which now contains the number of hills and valleys in the array.

The algorithm's time complexity is O(n), where n is the number of elements in nums, since it involves a single loop through the array. The space complexity is O(1) because we use a fixed amount of additional space.

This solution approach successfully counts the number of hills and valleys by using two pointers and a counter, effectively bypassing adjacent duplicates and considering them as part of the same hill/valley, thereby satisfying the problem's constraints and requirements.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider the array nums given by [2, 2, 3, 4, 3, 3, 2, 2, 1, 1, 2]. We want to find out how many hills and valleys this array contains. Looking at the array, we can visually identify one hill (comprising the element 4) and two valleys (comprising elements 3 at index 4 and 1 at index 8).

Now, following the provided solution approach:

  1. Initialize two pointers i = 1 and j = 0. Initialize the answer counter ans to 0.

  2. Start iterating from the second element to the second-to-last element:

    • At i = 1, nums[i] = 2 and nums[j] = 2. They are equal, so we continue without incrementing ans.
    • At i = 2, nums[i] = 3. Now we compare nums[i] with nums[j] (2) and nums[i+1] (4). Since 3 is neither a hill nor a valley, we move on, updating j to i.
    • At i = 3, nums[i] = 4, and it is greater than both nums[j] (3) and nums[i+1] (3), so we have found a hill. Increment ans to 1, and update j to i.
    • At i = 4, nums[i] = 3. It is less than both nums[j] (4) and nums[i+1] (3), so we have found a valley. Increment ans to 2, but do not update j because nums[i] is equal to nums[i+1].
    • We skip i = 5 since nums[i] = nums[i+1].
    • At i = 6, nums[i] = 2, which is less than both nums[j] (3) and nums[i+1] (2), but since nums[i] is equal to nums[i+1], we skip updating ans.
    • At i = 7, we skip since nums[i] = nums[i+1].
    • At i = 8, nums[i] = 1, and it is less than both nums[j] (2) and nums[i+1] (1), so we have found another valley. Increment ans to 3.

  3. There are no more elements to check, so we have now reached the end of the array. The value of ans is 3, which is the total number of hills and valleys in the array.

The process demonstrates how the algorithm effectively skips over equal elements, treats them as part of the same hill or valley, and correctly identifies distinct hills and valleys in compliance with the problem's definition.

Solution Implementation

1from typing import List
2
3class Solution:
4    def countHillValley(self, nums: List[int]) -> int:
5        # Initialize the count of hills and valleys
6        count = 0
7        # Initialize a pointer to track the last significant number (hill or valley)
8        last_significant_number_index = 0
9      
10        # Iterate over the array starting from the second element and stopping before the last
11        for i in range(1, len(nums) - 1):
12            # Skip if the current number is the same as the next, as it cannot be a hill or valley
13            if nums[i] == nums[i + 1]:
14                continue
15          
16            # Check if the current number is a hill by comparing with the last significant number and next number
17            if nums[i] > nums[last_significant_number_index] and nums[i] > nums[i + 1]:
18                count += 1
19            # Check if the current number is a valley by comparing with the last significant number and next number
20            elif nums[i] < nums[last_significant_number_index] and nums[i] < nums[i + 1]:
21                count += 1
22              
23            # Update the pointer to the last significant number as the current number
24            last_significant_number_index = i
25      
26        # Return the total count of hills and valleys found
27        return count
28
1class Solution {
2    public int countHillValley(int[] nums) {
3        // Initialize the counter for hills and valleys found.
4        int count = 0;
5
6        // Loop through the input array, checking for hills or valleys.
7        // The 'previousIndex' variable will track the index of the last
8        // element in the sequence that is not equal to the current element.
9        for (int currentIndex = 1, previousIndex = 0; currentIndex < nums.length - 1; ++currentIndex) {
10          
11            // Skip the current element if it's equal to the next one
12            // since we're looking for unique hills or valleys.
13            if (nums[currentIndex] == nums[currentIndex + 1]) {
14                continue;
15            }
16          
17            // Check for a hill: the current number is greater than both its adjacent numbers.
18            if (nums[currentIndex] > nums[previousIndex] && nums[currentIndex] > nums[currentIndex + 1]) {
19                count++;
20            }
21          
22            // Check for a valley: the current number is less than both its adjacent numbers.
23            if (nums[currentIndex] < nums[previousIndex] && nums[currentIndex] < nums[currentIndex + 1]) {
24                count++;
25            }
26          
27            // Update the previousIndex to the current index.
28            previousIndex = currentIndex;
29        }
30        // Return the total number of hills and valleys found.
31        return count;
32    }
33}
34
1class Solution {
2public:
3    int countHillValley(vector<int>& nums) {
4        int count = 0; // Initialize counter for hills and valleys to zero
5
6        // We use two pointers, 'previous' to keep track of the last distinct element
7        // and 'current' which will iterate through the vector, starting from index 1
8        for (int current = 1, previous = 0; current < nums.size() - 1; ++current) {
9          
10            // Skip over duplicate adjacent values
11            if (nums[current] == nums[current + 1]) {
12                continue;
13            }
14          
15            // Check if nums[current] forms a hill
16            if (nums[current] > nums[previous] && nums[current] > nums[current + 1]) {
17                ++count; // Increment count if we found a hill
18            }
19          
20            // Check if nums[current] forms a valley
21            if (nums[current] < nums[previous] && nums[current] < nums[current + 1]) {
22                ++count; // Increment count if we found a valley
23            }
24          
25            // Update 'previous' to the last distinct element's index
26            previous = current;
27        }
28      
29        return count; // Return the final count of hills and valleys
30    }
31};
32
1function countHillValley(nums: number[]): number {
2    // n holds the total number of elements in the input array nums.
3    const numberOfElements = nums.length;
4    // Initialize hillValleyCount to count the number of hills and valleys found.
5    let hillValleyCount = 0;
6    // Initialize previousValue to the first value of the nums array.
7    let previousValue = nums[0];
8
9    // Iterate over the array starting from the second element till the second last element.
10    for (let i = 1; i < numberOfElements - 1; i++) {
11        // currentValue holds the current element in the array.
12        const currentValue = nums[i];
13        // nextValue holds the next element in the array.
14        const nextValue = nums[i + 1];
15        // Continue to the next iteration if the current and next values are the same.
16        if (currentValue == nextValue) {
17            continue;
18        }
19        // Check if the currentValue is either a hill or a valley, and if so, increment hillValleyCount.
20        if ((currentValue > previousValue && currentValue > nextValue) || (currentValue < previousValue && currentValue < nextValue)) {
21            hillValleyCount += 1;
22        }
23        // Update previousValue to be the currentValue as we move forward in the array.
24        previousValue = currentValue;
25    }
26    // Return the total count of hills and valleys found in the array.
27    return hillValleyCount;
28}
29
Not Sure What to Study? Take the 2-min Quiz：

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), where n is the length of the input list nums. This is because the main operation of the code, iterating through the list, is done in a single pass from the second element to the second-to-last element. Each comparison operation within the loop is done in constant time.

Space Complexity

The space complexity of the code is O(1) (constant space complexity). This is because the space used by the variables ans, j, and i does not scale with the size of the input list nums. No additional data structures that scale with the input size are used.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫