5 ms Binary Search based neat easy to understand solution in Java with explanation. O(nlogn) Time. O(1) space.


  • 0
    P

    The main idea is that you the number of elements in the array will be more than the actual number of elements that should be present in the array.
    So we count the elements that are smaller than the middle element. if it more than it is supposed to be then the duplicate is in that part of the array. O(nlogn) time complexity because we will search the array logn times

    public int findDuplicate(int[] nums) {
    		int start = 1;
    		int end = nums.length;
    		int mid = 0;
    		while (start != end) {
    			int count = 0;
    			mid = (start + end) / 2;
    			for (int i = 0; i < nums.length; i++) {
    				if (nums[i] <= mid)
    					count++; 
    			}
    			if (count <= mid) // this side is fine. usual or less than usual elements are present this side.
    				start = mid + 1;
    			else // more than allowed elements are present this side.
    				end = mid;
    		}
    
    		return start;
    	}
    

Log in to reply
 

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