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


  • 0
    S

    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 {
    private:
        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);
        }
    public:
        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.