Simplest and clear solution with nice explanation


  • 1
    S

    // Assumption : the array is sorted in increasing order and then rotated
    // GAYLE LAAKMANN APPROACH - SIMPLEST

    class Solution {
    public:
        int findMin(vector<int> &num) {   
    
            int left = 0;
            int right = num.size() - 1;           
            
            while(left < right){
                
                // if no rotation
                if(num[left] < num[right]) return num[left];
                
                int mid = (left + right)/2;
    
                /*
                Either the Left or Right half must be normally ordered. Find out which half is normally ordered, the inflection point (minimum element)
                lies in the other half. Select the other half border coordinates carefully
                */
    
                if(num[left] < num[mid]){ // Left is normally ordered => the inflection point exists in [mid+1, right] which MAY NOT have a rotation Eg : 2,3,1         
                    left = mid+1;		// Special Edge Case : here 1 is inflection point in index [0th, 2nd]  but when when u consider [3rd, 3rd] then it does not have a rotation
                    					// The above "if no rotation check" comes to the rescue to take care of this kind of edge case wherever left = mid+1; is being done
                }
                else if(num[mid] < num[left]){ // Right is normally ordered => the inflection point exists in [left, mid] 
                    right = mid;				
                }
                else{
                    // now we have ->  num[left] == num[mid] 
                    if(num[mid] != num[right]) left = mid+1;
                    else {
                    	left++;
                    	right--;
                    }
                }
            }
            return num[right];
        }
    };

  • 0
    Q

    nice solution, thx very much. I rewrite the code to make it more concise. a little difference -- compared with last element.

    int findMin(vector<int>& nums) {
    	int left=0, right=nums.size()-1;
    	while(nums[left]>=nums[right] && left<right) {
    		int mid=left+((right-left)>>1);
    		if(nums[mid]>nums[right]) left=mid+1;
    		else if(nums[mid]<nums[right] || nums[mid]!=nums[left]) right=mid;
    		else { ++left, --right; }
    	}
    	return nums[left];
    }
    

Log in to reply
 

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