Sharing C++ O(log n) solution with geometrical intuition.


  • 0
    S
    class Solution {
    public:
    
        bool checkPeak(const vector<int> &num, int idx){
            int n = num.size();
            if (idx == 0)
                return (num[0] > num[1]);
            if (idx == n-1)
                return (num[n-1] > num[n-2]);
            
            return ((num[idx] > num[idx-1]) && (num[idx] > num[idx+1]));
        }
    
        int helper(const vector<int> &num, int head, int tail){
            if (head > tail) return head;
            
            int mid = (head + tail)/2;
            if (checkPeak(num, mid)) return mid; 
            
            if (num[mid] < num[mid-1])
                return helper(num, 0, mid-1);
            else
                return helper(num, mid+1, tail);
        }
    
        int findPeakElement(const vector<int> &num) {
            if (num.size() == 1) return 0;
            if (checkPeak(num, 0)) return 0;
            if (checkPeak(num, num.size()-1)) return (num.size()-1);
            
            return helper(num, 0, num.size()-1);
        }
    };
    

    First, as in all other O(log n) solutions. We look for an algorithm where we reduce the search space by half each time. Now, by problem definition, there is only one maxima if we plot the provided numbers. Also for the sake of the argument, assume the maxima is not at the bounds.

    Then, let's look at three points. Beginning, end, and a mid point. Here's the critical part, if the mid point has positive gradient, we can ignore the left half. This is because the only feasible case is where the the left half is monotonically increasing and the right half has a peak and falls off. Likewise, if the mid point has negative gradient, we can ignore the right half.

    Suggestions for improvements in the code is welcome!


Log in to reply
 

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