Find a peak element - PrismoSkills
Problem: A peak element is defined as an element which is NOT smaller than its immediate neighbors.
Two exceptions to a peak element are:
First element is a peak element if its not smaller than second element.
Last element is a peak element if its not smaller than second-last element.
For an array with all elements equal, all elements are peak elements.
Example: Peak elements in [5, 7, 3, 9, 10, 12] are 7 and 12
Solution: An O(n) solution for this problem is very easy.
Just loop over the elements of the array and if any element satisfies the peak element's condition, then return it.
However, this can be converted into a binary search (without the array being sorted) if we observe the following:
If an element is not the peak, then that element must be smaller than one of its neighbors.
If left neighbor is greater, then left half of the array must have a peak.
Similarly, if right neighbor is greater, then right half of the array must have a peak.
This can be used to divide our search for peak element into half every time we analyze an element for being the peak.
http://buttercola.blogspot.com/2015/11/zenefits-find-peak.html
The brute-force solution is quite easy. Just scan and compare. So the time complexity would be O(N).
However, as is required by the question, the solution should be in O(logn) time. We therefore must think of binary search.
The idea is:
Read full article from Find a peak element - PrismoSkills
Problem: A peak element is defined as an element which is NOT smaller than its immediate neighbors.
Two exceptions to a peak element are:
First element is a peak element if its not smaller than second element.
Last element is a peak element if its not smaller than second-last element.
For an array with all elements equal, all elements are peak elements.
Example: Peak elements in [5, 7, 3, 9, 10, 12] are 7 and 12
Solution: An O(n) solution for this problem is very easy.
Just loop over the elements of the array and if any element satisfies the peak element's condition, then return it.
However, this can be converted into a binary search (without the array being sorted) if we observe the following:
If an element is not the peak, then that element must be smaller than one of its neighbors.
If left neighbor is greater, then left half of the array must have a peak.
Similarly, if right neighbor is greater, then right half of the array must have a peak.
This can be used to divide our search for peak element into half every time we analyze an element for being the peak.
http://buttercola.blogspot.com/2015/11/zenefits-find-peak.html
A peak element is an element that is greater than its neighbors.
Given an input array where
num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that
num[-1] = num[n] = -∞.
For example, in array
[1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
The neighbor of an element A[i] is defined as A[i - 1] and A[i + 1]. Therefore, the peak element is iff A[i] > A[i - 1] && A[i] > A[i + 1].
The brute-force solution is quite easy. Just scan and compare. So the time complexity would be O(N).
However, as is required by the question, the solution should be in O(logn) time. We therefore must think of binary search.
The idea is:
-- If the middle of the array is the peak element, then just return the index.
-- If the left neighbor is greater than the middle, move to the left. The peak element must exist in the left half. That is because the num[-1] = num[n] = -inf.
-- The same, if the right neighbor is greater than the middle, move to the right.
public static int findPeakElement(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int lo = 0; int hi = nums.length - 1; while (lo + 1 < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) { return nums[mid]; } else if (nums[mid] < nums[mid - 1]) { hi = mid - 1; } else if (nums[mid] < nums[mid + 1]) { lo = mid + 1; } } if (nums[lo] > nums[hi]) { return nums[lo]; } else { return nums[hi]; } } 