## Monday, April 25, 2016

### LeetCode 162 - Find Peak Element

http://www.programcreek.com/2014/02/leetcode-find-peak-element/
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.
Assume we initialize left = 0, right = nums.length - 1. The invariant I'm using is the following:
nums[left - 1] < nums[left] && nums[right] > nums[right + 1]
That basically means that in the current interval we're looking, [left, right] the function started increasing to left and will eventually decrease at right. The behavior between [left, right] falls into the following 3 categories:
1) nums[left] > nums[left + 1]. From the invariant, nums[left - 1] < nums[left] => left is a peak
2) The function is increasing from left to right i.e. nums[left] < nums[left + 1] < .. < nums[right - 1] < nums[right]. From the invariant, nums[right] > nums[right + 1] => right is a peak
3) the function increases for a while and then decreases (in which case the point just before it starts decreasing is a peak) e.g. 2 5 6 3 (6 is the point in question)
As shown, if the invariant above holds, there is at least a peak between [left, right]. Now we need to show 2 things:
I) the invariant is initially true. Since left = 0 and right = nums.length - 1 initially and we know that nums[-1] = nums[nums.length] = -oo, this is obviously true
II) At every step of the loop the invariant gets reestablished. If we consider the code in the loop, we have mid = (left + right) / 2 and the following 2 cases:
a) nums[mid] < nums[mid + 1]. It turns out that the interval [mid + 1, right] respects the invariant (nums[mid] < nums[mid + 1] -> part of the cond + nums[right] > nums[right + 1] -> part of the invariant in the previous loop iteration)
b) nums[mid] > nums[mid + 1]. Similarly, [left, mid] respects the invariant (nums[left - 1] < nums[left] -> part of the invariant in the previous loop iteration and nums[mid] > nums[mid + 1] -> part of the cond)
As a result, the invariant gets reestablished and it will also hold when we exit the loop. In that case we have an interval of length 2 i.e. right = left + 1. If nums[left] > nums[right], using the invariant (nums[left - 1] < nums[left]), we get that left is a peak. Otherwise right is the peak (nums[left] < nums[right] and nums[right] < nums[right + 1] from the invariant).
I wanted to visually see how it works, so here's an example I worked out:
``````         5   5                           5
/ \ / \                         / \
4   4   4                       4  -∞
/         \                     /
3           3           3       3
/             \         / \     /
2               2       2   2   2
/                 \     /     \ /
-∞                   1   1       1
\ /
0
0 1 2 3 4 5 6 7 8 910111213141516171819 indices
2,3,4,5,4,5,4,3,2,1,0,1,2,3,2,1,2,3,4,5 (20 nums)
l                 m                   r l=0, m=9, r=19
l       m         r                     l=0, m=4, r= 9
l   m   r                     l=5, m=7, r= 9
l>m r                         l=5, m=6, r= 7
return n[l] > n[l + 1])? l : r``````
public int findPeakElement(int[] nums) { int N = nums.length; if (N == 1) { return 0; } int left = 0, right = N - 1; while (right - left > 1) { int mid = left + (right - left) / 2; if (nums[mid] < nums[mid + 1]) { left = mid + 1; } else { right = mid; } } return (left == N - 1 || nums[left] > nums[left + 1]) ? left : right; }

Key point here is that, at each mid, if you move towards the direction of semi-peak (`5,7,x - > move right`), you'll end up at some peak.
This problem is similar to Local Minimum. And according to the given condition, num[i] != num[i+1], there must exist a O(logN) solution. So we use binary search for this problem.
• If num[i-1] < num[i] > num[i+1], then num[i] is peak
• If num[i-1] < num[i] < num[i+1], then num[i+1...n-1] must contains a peak
• If num[i-1] > num[i] > num[i+1], then num[0...i-1] must contains a peak
• If num[i-1] > num[i] < num[i+1], then both sides have peak (n is num.length)
public int findPeakElement(int[] num) { return helper(num,0,num.length-1); } public int helper(int[] num,int start,int end){ if(start == end){ return start; }else if(start+1 == end){ if(num[start] > num[end]) return start; return end; }else{ int m = (start+end)/2; if(num[m] > num[m-1] && num[m] > num[m+1]){ return m; }else if(num[m-1] > num[m] && num[m] > num[m+1]){ return helper(num,start,m-1); }else{ return helper(num,m+1,end); } } }
public int findPeakElement(int[] nums) { int lo = 0, hi = nums.length-1; while(lo < hi){ if(lo +1== hi) return nums[lo] > nums[hi]? lo : hi; int mid = lo + (hi - lo)/2; if(nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) return mid; else if(nums[mid] > nums[mid-1] && nums[mid] < nums[mid+1]) lo = mid+1; else hi = mid-1; } return lo; }
X. Brute Force
http://blog.csdn.net/u010367506/article/details/41943309

```    int findPeakElement(const vector<int> &num) {
for(int i=1;i<num.size();i++){
if(num[i]<num[i-1])
return i-1;
}
return num.size()-1;
}```

```    public int findPeakElement(int[] num) {
int max = num[0];
int index = 0;
for(int i=1; i<=num.length-2; i++){
int prev = num[i-1];
int curr = num[i];
int next = num[i+1];

if(curr > prev && curr > next && curr > max){
index = i;
max = curr;
}
}

if(num[num.length-1] > max){
return num.length-1;
}

return index;
}
```

http://www.danielbit.com/blog/puzzle/leetcode/leetcode-find-peak-element
```    public int findPeakElement(int[] num) {
if (num==null) return -1;
if (num.length==1) return 0;
int n = num.length;
for (int i=0; i<n; ++i) {
if ( (i==0 && num[i]>num[i+1]) || (i==n-1 && num[i]>num[i-1]) || (i!=0 && i!=n-1 && num[i-1]<num[i] && num[i]>num[i+1]) ) return i;
}
return -1;
}```
http://www.jiuzhang.com/solutions/find-peak-element/

```    public int findPeak(int[] A) {
// write your code here
int start = 1, end = A.length-2; // 1.答案在之间，2.不会出界
while(start + 1 <  end) {
int mid = (start + end) / 2;
if(A[mid] < A[mid - 1]) {
end = mid;
} else if(A[mid] < A[mid + 1]) {
start = mid;
} else {
end = mid;
}
}
if(A[start] < A[end]) {
return end;
} else {
return start;
}
}```