Easy Java code, 1 ms, with good explanation.


  • 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!


  • 0
    Y

    What about this input for your Rotated Sorted Array II solution? [10,10,1,10,10,10,10,10,10]


Log in to reply
 

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