Very pleased with this one (C++)

  • 0

    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 {
        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.