Short Divide and Conquer Solution in C++ [AC]

  • 0

    The solution uses divide and conquer technique very similar to binary search. We will first find the mid index.

    • If the mid is the peak, we will return the index.
    • If the mid value is smaller than the value at mid-1, we will skip the right half and recur for the left half.
    • If the mid value is smaller than the value at mid+1, we will skip the left hald and recur for the right half.
    class Solution {
        int helper(vector<int>& arr, int n, int l, int h)
            int mid = l + (h-l)/2;
            if( (mid == 0 || arr[mid-1]<=arr[mid]) && (arr[mid]>= arr[mid+1] || mid == n-1))
                return mid;
            else if(arr[mid] < arr[mid-1] && mid>0)
                return helper(arr, n, l,mid-1);
            return helper(arr, n,mid+1, h);
        int findPeakElement(vector<int>& nums) {
            int high,low;
            high =nums.size();
            low = 0;
            int n = nums.size();
            return helper(nums, n, low, high);

Log in to reply

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