Easy to Understand Java solution O(log n) using Binary Search


  • 2
    N

    Seperated conditions to help understand quickly.

    public class Solution {
        public int singleNonDuplicate(int[] nums) {
            
            int low =0;
            int high = nums.length -1;
            int mid;
            boolean left;
            boolean leftFirst;
            boolean leftSecond;
    
            while(low<high)
            {
                mid = low + (high-low)/2;
            
                if(nums[mid]!=nums[mid-1] && nums[mid]!=nums[mid+1])
                return nums[mid];
                //conditions to be true if an element is in left side 
                leftFirst = (nums[mid] == nums[mid-1]) && (mid)%2==0; //if its the second occurence of that element 
                leftSecond = (nums[mid] == nums[mid+1]) && (mid)%2==1; //if its the first occurence of that element 
                left = leftFirst||leftSecond;  //if any of the above conditions are true, We will go left
                
                if(left)
                    high = mid-1;
                else
                    low = mid+1;
            }
            return nums[low];
        }
    }
    

  • 0
    L

    Why mid = low + (high-low)/2 ?


  • 0
    N
    This post is deleted!

  • 1
    N

    @leap20 low+high might get greater than Integer.MAX_VALUE and to prevent that we do that.
    For more details:
    https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html


  • 0
    L

    @namanrajpal16 Thanks for that! One last question: Why do you need mid%2==0 and mid%2==1


  • 1
    N

    @leap20 So as the code suggests, there are two conditions (leftFirst & leftSecond) that will decide we should consider left partition or right.
    let me explain:

    leftFirst: One of the two conditions to go left is : if it is the second occurrence of that digit(3 here) than mid should be even (even number of elements before it, because everything repeats twice)

    1     1    2    3    3    4    4    5    5
                        mid
    

    leftSecond: Another condition to go left is : if it is the first occurrence of that digit(4 here) than mid should be odd (odd number of elements before it, because everything repeats twice) :
    Considering a different example:

    1   2   2   3   3   4   4   5   5   6   6
                       mid
    

    IF any of the above conditions are true, we go left otherwise right.


  • 0
    L

    @namanrajpal16 Excellent explanation. Thanks!


  • 0
    I

    Two questions:

     if(nums[mid]!=nums[mid-1]
    
    1. Consider this example: [1,3,3,5,5].
      Eventually you'll be looking at the subarray [1,3], with low = 0, high = 1 which implies mid = 0. I think your array access nums[mid-1] would throw index out of bounds here. you should check for valid index, or did i miss something?
    return nums[low];
    
    1. Why? Shouldn't return nums[mid] be the one finding the right number? Once you exited the loop, the search was unsuccessful, you could return fail or throw. are you simply returning "something" in this case or is this actually needed for the answer to be correct?

    Good explanation otherwise!


  • 0
    I

    Update to my post above.

    1. is a bug, needs check
    2. when the first or last element is the answer, the search will terminate unsuccessfully, but at that point, since we know the array has 1 element that matches the condition, we just return it.
      e.g: [1,1,2] or [1,2,2]. // return nums[low] fixes this.

Log in to reply
 

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