Given a List, the following article shows ways to count elements which are either peak(x > y < z) or valley(x < y > z).
Input : test_list = [1, 2, 4, 2, 6, 7, 8, 3]
Output : 3
Explanation : (2, 4, 2), (4, 2, 6), (7, 8, 3) are peaks and valleys.
Input : test_list = [1, 2, 4, 5, 3, 2]
Output : 1
Explanation : (4, 5, 3) is peak.
Method 1 : Using loop
In this, we iterate for each element and check if its next and previous element is either smaller or larger than the current element. If found, the counter is incremented.
Python3
# initializing listtest_list = [1, 2, 4, 2, 6, 7, 8, 3]# printing original listprint("The original list is : " + str(test_list))res = 0for idx in range(1, len(test_list) - 1): if test_list[idx + 1] > test_list[idx] < test_list[idx - 1] or test_list[idx + 1] < test_list[idx] > test_list[idx - 1]: res += 1# printing resultprint("Peaks and Valleys count : " + str(res)) |
Output:
The original list is : [1, 2, 4, 2, 6, 7, 8, 3]
Peaks and Valleys count : 3
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 2 : Using list comprehension and len()
In this, we perform the task of getting peak and valleys using list comprehension and then len() is used to compute the exact count.
Python3
# initializing listtest_list = [1, 2, 4, 2, 6, 7, 8, 3]# printing original listprint("The original list is : " + str(test_list))# one-liner alternativeres = len([test_list[idx] for idx in range(1, len(test_list) - 1) if test_list[idx + 1] > test_list[idx] < test_list[idx - 1] or test_list[idx + 1] < test_list[idx] > test_list[idx - 1]])# printing resultprint("Peaks and Valleys count : " + str(res)) |
Output:
The original list is : [1, 2, 4, 2, 6, 7, 8, 3]
Peaks and Valleys count : 3
Time Complexity: O(n), where n is the length of the input list. This is because we’re using the list comprehension and len() which has a time complexity of O(n) in the worst case.
Auxiliary Space: O(1), as we’re not using any additional space other than the input list itself.
