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

  • 9

    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];
                   // If it is not greater than 0 (i.e) negative then the number is a duplicate
        return newList;

  • 1

    should be:


    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

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

  • 0

    @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

    @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.