Simple 2ms solution that uses the same approach as finding duplicates in an array of size n, where maximum in the array can be n.


  • 0
    C

    Simple 2ms solution that uses the same approach as finding duplicates in an array of size n, where maximum in the array can be n.
    Mark the value at the index represented by current pointer's value, negative. So that if you were to find a duplicate leading back to the same point you can tell if it's been visited before, at which point, you return that number.

    public int findDuplicate(int[] nums) {
            for(int i = 0; i < nums.length; i++) {
                int index = nums[i];
                if(index < 0) index *= -1;
                
                if(nums[index - 1] < 0)
                    return index;
                else
                    nums[index - 1] *= -1;
            }
            
            return -1;
        }
    

  • 0
    Y

    You must not modify the array (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.