2210. Count Hills and Valleys in an Array
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]
andnums[i] > nums[i+1]
, it means thatnums[i]
is a hill. We increment the answer counter. - If
nums[i] < nums[j]
andnums[i] < nums[i+1]
, it means thatnums[i]
is a valley. We increment the answer counter as well. - If
nums[i]
is equal tonums[i+1]
, we continue the iteration without changingj
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.
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:
- Initialize two pointers
i
andj
.i
starts from 1 since the first element cannot be a hill or valley, andj
starts from 0, which will keep track of the last index that has a different value fromnums[i]
. - Initialize a counter
ans
to 0 to keep track of the number of hills and valleys. - Start a loop from the second element (index 1) to the second-to-last element (index
len(nums) - 2
, since we will be checkingnums[i + 1]
). - 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]
andnums[i] > nums[i + 1]
, we have found a hill, incrementans
by 1. - If
nums[i] < nums[j]
andnums[i] < nums[i + 1]
, we have found a valley, incrementans
by 1. - Update the
j
pointer toi
as this comparison is complete, andi
had a different value thannums[i + 1]
.
- If
- 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
Initialize two pointers
i = 1
andj = 0
. Initialize the answer counterans
to0
. -
Start iterating from the second element to the second-to-last element:
- At
i = 1
,nums[i] = 2
andnums[j] = 2
. They are equal, so we continue without incrementingans
. - At
i = 2
,nums[i] = 3
. Now we comparenums[i]
withnums[j]
(2
) andnums[i+1]
(4
). Since3
is neither a hill nor a valley, we move on, updatingj
toi
. - At
i = 3
,nums[i] = 4
, and it is greater than bothnums[j]
(3
) andnums[i+1]
(3
), so we have found a hill. Incrementans
to1
, and updatej
toi
. - At
i = 4
,nums[i] = 3
. It is less than bothnums[j]
(4
) andnums[i+1]
(3
), so we have found a valley. Incrementans
to2
, but do not updatej
becausenums[i]
is equal tonums[i+1]
. - We skip
i = 5
sincenums[i] = nums[i+1]
. - At
i = 6
,nums[i] = 2
, which is less than bothnums[j]
(3
) andnums[i+1]
(2
), but sincenums[i]
is equal tonums[i+1]
, we skip updatingans
. - At
i = 7
, we skip sincenums[i] = nums[i+1]
. - At
i = 8
,nums[i] = 1
, and it is less than bothnums[j]
(2
) andnums[i+1]
(1
), so we have found another valley. Incrementans
to3
.
- At
-
There are no more elements to check, so we have now reached the end of the array. The value of
ans
is3
, 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
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.
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.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 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