My Java solution WITH explanation.


  • 0
    W
        if(nums == null || nums.length == 0)
            return -1;
        if(nums.length == 1)
            return nums[0];
        //use Binary search
        int firstIndex = 1;
        int lastIndex = nums.length - 1;
    
        //traverse array until it has reached the rotated segment of the array
        //then do BS on that segment only!
        while(firstIndex <= lastIndex){
            if(nums[firstIndex] < nums[firstIndex-1]){
                break;
            }
            firstIndex++;
        }
        
        //means its sorted normally -- normal BS on array
        if(firstIndex > lastIndex)
            firstIndex = 0;
        
        while(firstIndex <= lastIndex){
            int middleIndex = firstIndex + (lastIndex-firstIndex)/2;
            if (middleIndex-1 >= 0 && nums[middleIndex-1] < nums[middleIndex]){ 
                lastIndex = middleIndex - 1;
            }else if (middleIndex+1 < nums.length && nums[middleIndex+1] < nums[middleIndex]){
                firstIndex = middleIndex + 1;
            }else{
                return nums[middleIndex];
            }
        }
        
        return -1;
    

    So, my thought process goes as follows:-

    1. Traverse array until we have found the rotated part of the array i.e. an element that is < than its predecessor.
    2. If none is found, then it can be assumed to be a typical sorted array and re-calibrate the firstIndex value.
    3. Either way, the firstIndex value is updated accordingly and the binary search algorithm works on whichever part of the array that the firstIndex value dictates.

    Feel free to provide feedback on this implementation and if it could be improved upon.


Log in to reply
 

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