O(logN) Solution JavaCode


  • 95
    X

    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)

    Here is the code

    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);
    
            }
            
        }
    }

  • 0
    H
    This post is deleted!

  • -5
    R

    in your code
    if(start == end)
    return start;

    array is not sorted, how do you get correct answer for say. 0 1 2 3 0


  • 0
    D

    start, end is the index, start ==end means there is only one element.


  • 0
    R

    ok, i mis-read it, thanks!


  • 0
    S

    So when peak at both side, just go to right side?


  • 0
    N

    I was cheated by you.haha


  • 1
    G

    Choose any side does not matter. Any peak is Ok as per the Question description.


  • 0
    C

    the statement "If num[i-1] > num[i] > num[i+1], then num[0...i-1] must contains a peak" doesn't apply on test case [7, 6, 5, 3, 2, 5, 4].


  • 0
    S

    7 is the peak here (applicable as per question)..


  • 0
    I

    thanks, great solution!


  • 0
    I

    Great solution! Accroding to your code , I write another program that return the bottom element of the list.

    public int findBottomElement(int[] num, int left, int right) {
            if (left == right) {
                return left;
            } else if (left + 1 == right) {
                if (num[left] < num[right]) {
                    return left;
                }
                return right;
            } else {
                int mid = (left + right) / 2;
                if (num[mid] < num[mid+1] && num[mid] < num[mid-1]) {
                    return mid;
                } else if (num[mid] < num[mid+1] && num[mid] > num[mid-1]) {
                    return findBottomElement(num, left, mid-1);
                } else {
                    return findBottomElement(num, mid+1, right);
                }
            }
        }
    
        public int findBottomElement(int[] num) {
            int left = 0, right = num.length - 1;
            return findBottomElement(num, left, right);
        }

  • 10
    H

    My Iterative code with similar idea.

    public class Solution {
    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;
    }
    

    }


  • 0
    G

    Great solution! Can you tell me why "num[i] != num[i+1], there must exist a O(logN) solution."?


  • 0
    L

    I like your explanation!


  • 0
    L

    @xctom Hi please check output for this case:[1,0,2,3,4,5,6]


  • 0
    Q

    This code doesn't work for the input "[3,2,2,2,1]".


  • 1
    J

    @rohitkgp if there is only 1 element, return start


  • 0
    J

    @qzhang72 said in O(logN) Solution JavaCode:

    This code doesn't work for the input "[3,2,2,2,1]".

    There wouldn't be same numbers next to each other because of the specification of the question.


  • 0

    smart solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.