Java solution with explanation - O(log n)


  • 0
    G

    class Solution {
    public int singleNonDuplicate(int[] nums) {
    // initialize lower index
    int low = 0;
    // initialize higher index
    int high = nums.length -1;

    //condition for while looping
        while (low < high){
            //mid point of array
            int mid = (low + high) / 2;
            
            // for example : [1,1,2,3,3], in this case it will return element at middle index
            if((nums[mid] != nums[mid+1]) && (nums[mid] != nums[mid-1])){
                return nums[mid];
            }
            
            // for example : [1,1,3,3,4,4,5,5,6], in this case it will return low index as next right to mid
            else if(nums[mid] == nums[mid+1] && mid%2 == 0){
                low = mid+1;
            }
            
            // for example : [1,1,3,3,4,4,5,5,6,6,9], in this case it will return low index as next right to mid
               else if((nums[mid] == nums[mid -1]) && mid%2 ==1){
                   low = mid+1;
               }  else{
                   
                   // for ex: [1,1,2,2,4,4,5,5,9], in this case it will return high index as left to mid
      high = mid-1;
    

    }

    }
    return nums[low];
    }
    }


Log in to reply
 

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