Peak and Pride
Let's call an array A a mountain if the
following properties hold:
- A.length >= 3
- There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
Given an array that is definitely a mountain,
return any i such that A[0] < A[1] < ... A[i-1]
< A[i] > A[i+1] > ... > A[A.length - 1].
Example 1:
Input: [0,1,0]
Output: 1
Example 2:
Input: [0,2,1,0]
Output: 1
If you
play close attention to the problem, it actually ends up being much simpler
than the whole problem statement suggests. Since the input is confirmed to be a
mountain (hence you don’t need to check whether it is a mountain or not), then
all you really need is to find the max element in the array! Now even if the question
was to determine whether the input was a mountain or not, you could still find
the max and then do an O(n) to determine whether that max is the peak of the
mountain or not. Code is below.
Below you’ll also find a screenshot of our
Pride Month experience (click here to check it out: www.bing.com and type “pride mon”). This is a tiny way to celebrate diversity, inclusion and equality during these times when these values are not being properly celebrated by many of our politicians.
Cheers, Marcelo.
public class Solution
{
public int PeakIndexInMountainArray(int[] A)
{
int max = Int32.MinValue;
int maxIndex = -1;
for (int i = 0; i < A.Length; i++)
{
if (A[i] > max)
{
max = A[i];
maxIndex = i;
}
}
return maxIndex;
}
}
Comments
Nice simple solution. Although, I think you can do a binary search to find the max element to solve it in O(log n). :-)
Reply DeleteYeah thinking about it more and knowing that the mountain property is guaranteed, I think you’re right!
DeleteAn excellent observation, Marcelo! The C++ implementation of this idea is, as always, more concise than C# :P and looks like:
Reply Deleteclass Solution {
public:
int peakIndexInMountainArray(const vector& A) {
return distance(A.cbegin(), max_element(A.cbegin(), A.cend()));
}
};
but a slightly more verbose implementation below takes advantage of another observation - for a given index i if an element to its left is greater or equal to it, a peak could only be on its left (i-1 or further to its left), if an element to its right is less than or equal to it, a peak could only be on its right (i+1 or further to its right) and otherwise A[i-1] < A[i] > A[i+1] and we have found the peak. The code is:
class Solution {
public:
int peakIndexInMountainArray(const vector& A) {
int left = 1;
int right = A.size() - 2;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid-1] >= A[mid]) {
right = mid - 1;
} else if (A[mid] <= A[mid+1]) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
};
https://leetcode.com/problems/peak-index-in-a-mountain-array/discuss/141301/log(N)-solution-based-on-binary-search-in-C++.
Cheers,
Taras
Post a Comment
[γγ¬γΌγ ]