You are given an array on n-elements. An extrema is an elements which is either greater than its both of neighbors or less than its both neighbors. You have to calculate the number of local extrema in given array.
Note : 1st and last elements are not extrema.
Examples :
Input : a[] = {1, 5, 2, 5}
Output : 2
Input : a[] = {1, 2, 3}
Output : 0
Approach :For calculating number of extrema we have to check whether an element is maxima or minima i.e. whether it is greater than both of its neighbors or less than both neighbors. For this simply iterate over the array and for each elements check its possibility of being an extrema.
Note: a[0] and a[n-1] has exactly one neighbour each, they are neither minima nor maxima.
Python3
# Python 3 to find# number of extrema# function to find# local extremumdef extrema(a, n): count = 0 # start loop from # position 1 till n-1 for i in range(1, n - 1) : # only one condition # will be true # at a time either # a[i] will be greater # than neighbours or # less than neighbours # check if a[i] if # greater than both its # neighbours, then add # 1 to x count += (a[i] > a[i - 1] and a[i] > a[i + 1]); # check if a[i] if # less than both its # neighbours, then # add 1 to x count += (a[i] < a[i - 1] and a[i] < a[i + 1]); return count# driver programa = [1, 0, 2, 1 ]n = len(a)print(extrema(a, n))# This code is contributed by Smitha Dinesh Semwal |
Output :
2
Time Complexity: O(n) where n is size of input array. This is because a for loop is executing from 1 to n.
Space Complexity: O(1) as no extra space has been used.
Please refer complete article on Number of local extrema in an array for more details!
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!