Write the definition of a function named countLocalMinima that recieves an array
ID: 3664122 • Letter: W
Question
Write the definition of a function named countLocalMinima that recieves an array of doubles and an integer indicating the number of elements in the array . The function returns the number of elements that are "local minima", that is those elements that are in between two other elements that are larger . For example, if the array contained 3 4 5 2 4 12 40 30 28 35 80 70 50 21 25 9 the function would return 3 because 2, 28, 21 in the list are "local minima". If the array contained 4 5 6 7 8 9 the function would return 0 because there are no local minima. Likewise, if the array contained 4 5 6 7 5 3 1 again the function would return 0. If the array contained 10 8 5 8 9 the function would return 1 since there is but one local minimum, 5.
Explanation / Answer
First we need to understand that if in an array of unique integers first two numbers are decreasing and last two numbers are increasing there ought to be a local minima. Why so? We can prove it in two ways. First we will do it by negation. If first two numbers are decreasing, and there is no local minima, that means 3rd number is less than 2nd number. otherwise 2nd number would have been local minima. Following the same logic 4th number will have to be less than 3rd number and so on and so forth. So the numbers in the array will have to be in decreasing order. Which violates the constraint of last two numbers being in increasing order. This proves by negation that there need to be a local minima
We can prove this in some other way also. Suppose we represent the array as a 2-D graph where the index of the numbers in the array represents the x-coordinate. and the number represents the y-coordinate. Now for the first two numbers, derivative will be negative, and for last two numbers derivative will be positive. So at some point the derivative line will have to cross the x axis. As the array contains only unique elements there cannot be a derivative point on the x axis. Because that will mean that two consecutive index having same number. So for any intersection of x axis by the derivative line will be a local minima.
We will solve this problem in O(log n) time by divide and conquer method. We will first check the mid index of the array. If it is smaller than its left and right, then it is the answer. If it is bigger than the left number then from start to left we have a sub problem, and as we proved already that starting with decreasing and ending with increasing sequence array will have to have a local minima, we can safely go to the left subarray. Otherwise if mid is bigger than its right, then we go to the right subarray. This way we guarantee a O(log n) algorithm to find any of the local minima present in the array.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.