This is a pretty classic problem. You can see it's detailed description in Find Peak Element.
The most easy way to solve to this problem is just make one pass for the input like below.
function findPeakElement(nums: number[]): number {
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
return i;
}
}
return nums.length - 1;
};
As you can see, the code is very simple, we only need to find the first element which is bigger than next element.
But in this way, the time complexity is O(n), how can we make it O(log(n))? To make this happen, the first algotihm comes to my mind is binary search. So the problem becomes how can we apply binary search into this problem?
Well, to find one peak elment, there are 3 cases.
First is increaing array numbers:
[1, 2, 3, 4, 5]
Second is decreasing array numbers:
[5, 4, 3, 2, 1]
Third is first increasing and then decreasing:
[1, 3, 5, 4, 2]
So the key is, for every iteration among the binary search, we compare current middle value nums[mid] with its next value nums[mid+1]. If nums[mid] > nums[mid+1], then there must exist a peak element on the left. Else, then there must exist a peak element on the right.
For example, for 3 cases above, in the first iteration, the mid index is 2, so situations are like below.
[1, 2, 3, 4, 5], index 2 has value 3, 3 < 4, peak element on the right(nums.slice(3))
[5, 4, 3, 2, 1], index 2 has value 3, 3 > 2, peak element on the left(nums.slice(0, 3))
[1, 3, 5, 4, 2], index 2 has value 5, 5 > 4, peak element on the left(nums.slice(0, 3))
So, follow this process recursively, we can find one peak element.
function _findPeakElement(nums: number[], left: number, right: number): number {
if (left === right) return left;
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] > nums[mid + 1]) {
return _findPeakElement(nums, left, mid);
} else {
return _findPeakElement(nums, mid + 1, right);
}
}
function findPeakElement(nums: number[]): number {
return _findPeakElement(nums, 0, nums.length - 1);
};
We can do this process iterately also.
function findPeakElement(nums: number[]): number {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
In leetcode, there is also a problem Find a Peak Element II. It's like a 2d version of peak element finding problem.
However, even though we have develop an intuition on how to sovle the 1d version, it is not easy to understand how to do it in 2d version.
Can we simple run the 1d version solution on every row and every column? No, because the solution just found 1 peak element, not all of them, so there is no guarantee that we can find the same element which is both peak element in row and in column. In other words, we can't do it in O(log(m)log(n)) time.
But we can do it in O(log(m)n) or O(mlog(n)) time. We can calaulate the max value on one dimension and use the binary search solution on another dimension. Now let's see how it works.
Say the grid is like below.
index
0 1 2 3 4
0 . . . . .
1 . . . . .
2 . . . . .
3 . . . . .
4 . . . . .
First, we move to the middle row, which is the row with index 2. Then we find the max value of the row, suppose the max value is x like below.
index
0 1 2 3 4
0 . . . . .
1 . . . . .
2 . . . x .
3 . . . y .
4 . . . . .
Then we compare x with next value on the grid, which is y. If x < y is true, just like in 1d version, we drop the first part. Now we have only half the grid.
index
0 1 2 3 4
...(dropped)
3 . . . . .
4 . . . . .
Because x is the max value and x < y, then we know for sure the max value on the row with index 3 is bigger than any value on the row with index 2.
Now follow the same process, we calculate the middle row, which is the row with index 3, then find its max value, we still use x.
index
0 1 2 3 4
...(dropped)
3 . . x . .
4 . . y . .
We compare the max value x with its next value y.
Now, if x>y, then x is the peak element. How come? because x is max value of the row, so row dimension is done. Because x>y and x is bigger than any value than values in row with index 2, then column demension is done. So in this case, x is the peak element.
If x<y, can we draw the conclusion that y is the peak element? No, because y may not bigger than element on the left or right. So what now? Now we find the max value of the row with index 4, suppose it is z.
index
0 1 2 3 4
...(dropped)
3 . . x . .
4 . . y . z
Because z is the max value of the row, so row is done. Because x<y and y<z, then x<z. Because x is the max value of row with index 3, so z is bigger than any values in the row with index 3. So column is done. So in this case, z is the peak element.
As you can see, for every step, we use max value to rule out one dimension(max value must be peak element), then we apply the binary search approach on another dimension. In above example, we calculate the max value of each row. Same approach goes with calculating max value on each column.
OK, now let's see the process in code.
// find max value, return [value, index]
function findMax(nums: number[]): [number, number] {
const result: [number, number] = [Number.MIN_SAFE_INTEGER, -1];
for (let i = 0; i < nums.length; i++) {
if (nums[i] > result[0]) {
result[0] = nums[i];
result[1] = i;
}
}
return result;
}
function findPeakGrid(mat: number[][]): number[] {
let startRowIndex = 0;
let endRowIndex = mat.length - 1;
while (startRowIndex < endRowIndex) {
const midRowIndex = startRowIndex + Math.floor((endRowIndex - startRowIndex) / 2);
const [maxValue, maxIndex] = findMax(mat[midRowIndex]);
const nextValue = mat[midRowIndex + 1][maxIndex];
// compare current max value with it's next value
// so we can rule out half grid
if (maxValue > nextValue) {
endRowIndex = midRowIndex;
} else {
startRowIndex = midRowIndex + 1;
}
}
// now we find target row, then we calculate max row value
const rowIndex = startRowIndex;
const [_, colIndex] = findMax(mat[rowIndex]);
return [rowIndex, colIndex];
};