Easy (nLogn) Java solution using Sorting and Binary Search.


  • -4
    V
    1. Idea is to sort the array first which itself is NLogN.
    2. Now there is a small modification in binary search. If mid element is >= (mid + 1) then there is number which is skipped from left part of the array and Hence duplicate lies on the other part.

    Total complexity is (NlogN + LogN) = O(NLogN)

    Note : I took hint from TAGS mentioned in the question iteself. Any improvement or modification would be appreciated. :D

    public int findDuplicate(int[] nums) {
                Arrays.sort(nums);
                int lo = 0 ; 
                int high = nums.length - 1 ;
                int mid = -1;
                while(lo < high){
                    mid = lo + (high - lo)/2 ;
                    if(mid > 0 && nums[mid] == nums[mid -1]){ // if mid element is duplicate
                        return nums[mid];
                    }else if(mid + 1 < nums.length && nums[mid] == nums[mid + 1]){ // if mid element is duplicate.
                         return nums[mid];
                    }else if(nums[mid] >= mid + 1){ // change lo and high according to mid value
                        lo = mid + 1;
                    }else{
                        high = mid - 1;
                    }
                }
                return 0;
            }

  • 3
    T

    This solution ignores the firs requirement:

    You must not modify the array (assume the array is read only).


  • 0
    V

    i missed that :(


  • 0
    X

    assume the array is read only


Log in to reply
 

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