Menu
I am given an array of integers. I have to find a peak element in it. An array element is peak if it is NOT smaller than its neighbors. For corner elements,consider only one neighbor.
For example:
For input array {10, 20, 15, 2, 23, 90, 67} there are two peak elements: 20 and 90. I need to return any one peak element.
The solution i tried is a linear scan of array and i found a peak element. The worst case time complexity of this method would be O(n).
Can we find the peak element in worst time complexity better than O(n)?
655
The peak element in an array is an array element which is not smaller than it's neighbours. For example, given an array of {6,7,10,12,9} 12 is the peak element of the array. Another example is an array of {8,15,9,2,23,5} in this case, there are two peak elements:15 and 23.
If input array is sorted in strictly increasing order, the last element is always a peak element. For example, 50 is peak element in {10, 20, 30, 40, 50}. If the input array is sorted in strictly decreasing order, the first element is always a peak element. 100 is the peak element in {100, 80, 60, 50, 20}.
The peak element is an element that is greater than its neighbors. Suppose we have an input array nums, where nums[i] ≠ nums[i+1], search for a peak element and return its index. The array can hold multiple peak elements, in that case return the index to any one of the peak elements.
Yes, you can do it in O(log n) using an idea similar to binary search. Point to the middle of the vector and check its neighbours. If it is greater than both of its neighbours, then return the element, it is a peak. If the right element is greater, then find the peak recursively in the right side of the array. If the left element is greater, then find the peak recursively in the left side of the array.
162
Yes, it is possible to find it in better time complexity. Using devide and conquer method
Following link will help you. http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf
33
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
