Very pleased with this one (C++)


  • 0
    I

    I was given this in a real interview about a year ago (with Palantir), and I made a mess out of it - mainly because I did not tidy up the boundary conditions.

    This one is watertight - or at least I am pretty confident that it is. If the recursive call hits a continuously ascending statement, it will return its first element as the definitive answer if the chop falls on the correct side of the rotation - i.e. outside the rotation "kink".

    class Solution {
    public:
        int searchMin(vector<int>& nums, int start, int end) {
            
            if ((start==end) || (nums[start]<nums[end]))
                return nums[start];
            
            int middle = (end+start)/2;
            if ( (nums[start]<=nums[middle]) && (nums[middle+1]<=nums[end]) && (nums[middle]>=nums[middle+1])) 
                return nums[middle+1];
            if (nums[start]>nums[middle])
                return searchMin(nums, start, middle);
            if (nums[middle+1]>nums[end])
                return searchMin(nums, middle+1, end);
        }
    
        int findMin(vector<int>& nums) {
            return searchMin(nums, 0, nums.size()-1);
        }
    };

Log in to reply
 

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