Wednesday, June 10, 2020

Leetcode Medium - Find Peak Element

Following is my Solution to Problem #162: Find Peak Element. Feel free to discuss and/or add your comments.

class Solution {
    public int findPeakElement(int[] nums) {
        
        if (nums.length ==1)
            return 0;
        
        for (int i=1; i<nums.length; i++)
            if (nums[i]<nums[i-1]) {
                return i-1;
            }
        
        return nums.length-1;
    }
}

There's a faster solution that guarantees answer in O(lg(n)) time. It uses Binary Search trick.

class Solution {
    public int findPeakElement(int[] nums) {
        
        if (nums.length ==1)
            return 0;
        
        int min = 0;
        int max = nums.length-1;
        while (min<max) {
            int mid = min+ (max-min)/2;
            
            if (nums[mid]<nums[mid+1])
                min = mid+1;
            else
                max = mid;
        }
        
        return min;
    }
}

No comments:

Post a Comment

Featured Post

interviewBit Medium: Palindrome Partitioning II

Problem Name:  Palindrome Partitioning II Problem Description : https://www.interviewbit.com/problems/palindrome-partitioning-ii/ Problem Ap...