Java Easy to understand solution without extra space and in O(n) time


  • 8

    The concept here is to negate each number's index as the input is 1 <= a[i] <= n (n = size of array). Once a value is negated, if it requires to be negated again then it is a duplicate.

    '''
    public List<Integer> findDuplicates(int[] nums) {

        List<Integer> newList = new ArrayList<Integer>();     // creating a new List
        for(int i=0;i<nums.length;i++){  
           int index =Math.abs(nums[i]);             // Taking the absolute value to find index
           if(nums[index-1] >0){ 
                    nums[index-1] = - nums[index-1];
            }else{
                   // If it is not greater than 0 (i.e) negative then the number is a duplicate
                    newList.add(Math.abs(nums[i])); 
            }
        }
        return newList;
    }

  • 1
    R
    newList.add(Math.abs(index[i])); 
    

    should be:

    newList.add(Math.abs(nums[i])); 
    

    Otherwise great solution!


  • 0

    @rostyys Thanks for letting me know ! That is right. I have updated it. Was trying to make it more readable.. And changed a few values. That's why the mistake.


  • 0
    T

    Essentially the same idea
    0_1489475377665_Screen Shot 2017-03-14 at 3.09.12 AM.png


  • 0
    V

    @gayathri3 Hi gayathri, there are chances that code might throw runtime exception if int index=Math.abs(nums[i]) returns index value more than the size of the array.


  • 0
    N

    @vishali123 No, that won't happen as the condition in the question states that 1 <= a[i] <= n. All elements are less than the size of array, so if n = 10, then no element >10


Log in to reply
 

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