Can anybody help me in finding out what's wrong with this code?8 test cases are failing.


  • 0
    A
    /* Input:
    [1,2,3,4,5]
    Output:
    5
    Expected:
    1
    This is the 139th test case which is failing*/
    
    class Solution {
    public:
    int findpivot(vector<int>& nums,int low,int high)
    {
        if(low>high) return -1;
        if(low==high) return low;
        int mid=(low+high)/2;
        if(mid<high && nums[mid]>nums[mid+1])
            return mid;
        if(low<mid && nums[mid-1]>nums[mid])
            return mid-1;
        if(nums[low]>=nums[mid])
            return findpivot(nums,low,mid);
        else
            return findpivot(nums,mid+1,high);
    }
        int findMin(vector<int>& nums) {
            if(nums.size()==1) return nums[0];
            int n=findpivot(nums,0,nums.size()-1);
            if(n==0 && nums[n]<nums[n+1]) return nums[n];
            if(n==-1 || n<nums.size()-1)
             return nums[n+1];
            else
            return nums[(n+1)%nums.size()];
        }
    };

  • 0
    D

    The problem lies in your findpivot() method. If the input is fully sorted (not rotated), your code can't find the right pivot point.
    Suppose you want to findpivot() to return -1 if input is fully sorted, the following code works (just modify the first line of findpivot()

    class Solution {
    public:
    int findpivot(vector<int>& nums,int low,int high)
    {
        if(low>high ***|| nums[low]<nums[high]***) return -1;
        if(low==high) return low;
        int mid=(low+high)/2;
        if(mid<high && nums[mid]>nums[mid+1])
            return mid;
        if(low<mid && nums[mid-1]>nums[mid])
            return mid-1;
        if(nums[low]>=nums[mid])
            return findpivot(nums,low,mid);
        else
            return findpivot(nums,mid+1,high);
    }
        int findMin(vector<int>& nums) {
            if(nums.size()==1) return nums[0];
            int n=findpivot(nums,0,nums.size()-1);
            if(n==0 && nums[n]<nums[n+1]) return nums[n];
            if(n==-1 || n<nums.size()-1)
             return nums[n+1];
            else
            return nums[(n+1)%nums.size()];
        }
    };

  • 0
    A

    It got accepted.Thank you :)


Log in to reply
 

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