Easy Java solution, for both the problems (Find Minimum in Rotated Sorted Array I and II).


  • 1
    S

    Compare whether the 'mid' is equal to 'high' and 'low', if it is then it can be of two types, i.e. 3,3,3,3,2,1,3 or 3,2,1,3,3,3,3.

    So it is not clear whether to go right or left, but we can make a decision by comparing with 'mid - 1', if it equal to 'mid-1', then the minimum element is in the right, so 'low = mid + 1', else if it is not equal to 'mid - 1' then minimum element has to be on the left side, so 'high = mid'. The rest is same as Find Minimum in Rotated Sorted Array 1 problem.

    Find Minimum in Rotated Sorted Array II solution

    public class Solution {
        public int findMin(int[] nums) {
    		if(nums == null || nums.length == 0) {
    			return 0;
    		}
    		int length = nums.length;
    
    		if(length == 1) {
    			return nums[0];
    		}
    		
    		int low = 0, high = nums.length - 1, mid = 0;
    
            while(low < high) {
                mid = low + ((high - low ) >>> 1);
        
                if(nums[mid] == nums[high]) {
                    if(nums[mid] == nums[low]) {
                        if(mid > 0 && nums[mid] != nums[mid - 1]) {
                            high = mid;
                        }
                        else {
                            low = mid + 1;
                        }
                    }
                    else {
                        high = mid;
                    }
                }
                else if(nums[mid] < nums[high]) {
                    high = mid;
                }
                else {
                    low = mid + 1;
                }
            }
            return nums[low];
    	}
    }
    

    Find Minimum in Rotated Sorted Array 1 solution

    public class Solution {
        public int findMin(int[] nums) {
            if(nums == null || nums.length == 0) {
                return 0;
            }
            
            int length = nums.length;
            if(length == 1) {
                return nums[0];
            }
            
            int low = 0;
            int high = length - 1;
            int mid = 0;
            
            while(low < high) {
                mid = low + ((high - low) >>> 1);
                if(nums[mid] < nums[high]) {
                    high = mid;
                }
                else {
                    low = mid + 1;
                }
            }
            return nums[low];
        }
    }
    

    Let me know what you think. Thanks!


Log in to reply
 

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