LeetCode: Find Peak Element (attention to data types)
https://leetcode.com/problems/find-peak-element/, problem statement
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.
Straightforward code, the only caveat is the line in yellow above. It gives you a hint to pay attention to the data types: instead of using an int, use a long and in that case you won't have to worry about boundary conditions. Code below.
public class Solution
{
public int FindPeakElement(int[] nums)
{
for (int i = 0; i < nums.Length; i++)
{
long prev = Int64.MinValue;
if (i - 1 >= 0) prev = nums[i - 1];
long next = Int64.MinValue;
if (i + 1 < nums.Length) next = nums[i + 1];
if ((long)nums[i] > prev && (long)nums[i] > next) return i;
}
return -1;
}
}
Not sure, why this problem is listed as medium, but it's definitely a good warm-up problem for edge case checking. Even though your solution is pretty nice, it can certainly be improved from perf standpoint by reducing the number of if statements inside of loop. Smart compilers try to do this automagically, but by moving out edge cases, the solution in my opinion is almost written problem description, so it's a win for perf (6ms) and readability :)
ReplyDeleteThis time my solution is pretty different:
class Solution {
public:
int findPeakElement(const vector& nums) {
if (nums.size() == 1 || nums[0] > nums[1]) return 0;
if (nums.back() > nums[nums.size()-2]) return nums.size()-1;
for (int i = 1; i < nums.size() - 1; ++i) {
if (nums[i-1] < nums[i] && nums[i] > nums[i+1]) return i;
}
return -1;
}
};
Thanks for sharing!
Indeed, wondering if this solution in C# would be more efficient though.
Deletelooks like it's not %)
Deletepublic class Solution {
public int FindPeakElement(int[] nums) {
if (nums.Length == 1 || nums[0] > nums[1]) return 0;
if (nums[nums.Length-1] > nums[nums.Length-2]) return nums.Length-1;
for (int i = 1; i < nums.Length - 1; ++i) {
if (nums[i-1] < nums[i] && nums[i] > nums[i+1]) return i;
}
return -1;
}
}
the report says that it takes 142ms to run it... Oh well - I should not trust my intuition, especially when it comes to managed language performance and JIT :)
hm, I start to doubt the quality of the measurements coming from the leetcode. I also ported this solution to Java
Deletepublic class Solution {
public int findPeakElement(int[] nums) {
if (nums.length == 1 || nums[0] > nums[1]) return 0;
if (nums[nums.length-1] > nums[nums.length-2]) return nums.length-1;
for (int i = 1; i < nums.length - 1; ++i) {
if (nums[i-1] < nums[i] && nums[i] > nums[i+1]) return i;
}
return -1;
}
}
and leetcode says that it takes 0ms to run all tests %)