Simple O(logn) and O(n) C++ implementations


  • 1
    X

    O(logn) iteration implementation:

    class Solution {
    public:
        int findPeakElement(vector<int>& nums) {
            int start = 0, end = nums.size() - 1;
            while (start < end - 1) {
                int mid = (start + end) / 2;
                if (nums[mid] < nums[mid - 1]) end = mid - 1;
                else if (nums[mid] < nums[mid + 1]) start = mid + 1;
                else return mid;
            }
            
            return start < end && nums[start] < nums[end] ? end : start;
        }
    };
    

    O(logn) recursive implementation (just for fun :)

    class Solution {
    public:
        int findPeakElement(vector<int>& nums) {
            return findPeak(nums, 0, nums.size()-1);
        }
        
    private:
        int findPeak(const vector<int> &nums, int start, int end) {
            if (start == end) return start;
            if (start + 1 == end) return nums[start] > nums[end] ? start : end;
            
            int mid = (start + end) / 2;
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) return mid;
            if (nums[mid] < nums[mid + 1]) return findPeak(nums, mid + 1, end);
            if (nums[mid] < nums[mid - 1]) return findPeak(nums, start, mid - 1);
        }
    };
    

    O(n) implementation:

    class Solution {
    public:
        int findPeakElement(vector<int>& nums) {
            int i = 0;
            while (i < nums.size() - 1 && nums[i] < nums[i+1]) i++;
            
            return i;
        }
    };

Log in to reply
 

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