Java solution without destroying the input array. O(n) time. O(1) space.


  • 17
    B

    Code:

    public class Solution {

    public List<Integer> findDuplicates(int[] nums) {
         List<Integer> result = new ArrayList<Integer>();
        if(nums == null)
            return result;
        for(int i=0; i<nums.length; i++){
            int location = Math.abs(nums[i])-1;
            if(nums[location] < 0){
                result.add(Math.abs(nums[i]));
            }else{
                nums[location] = -nums[location];
            }
        }
        for(int i=0; i<nums.length; i++)
            nums[i] = Math.abs(nums[i]);
       
        return result;
    }
    

    }


  • 0
    R

    Could you please explain the logic and intuition behind the solution?

    Thanks,


  • 5
    A

    He/She is still using the input array as a way to mark which elements has been seen by making the number at the index, negative when it has already been used. At the end, all the numbers are restored to their respective positive value.


  • 0
    K

    Elegant solution by using the value as index, and mark the corresponding value to negative..


  • 0
    W

    The original array was altered during the process but restored in the end. Extra time could have been saved if no restoration was done.


  • 0
    A
    This post is deleted!

  • 0
    T

    @rpmnitp He use "-" symbol to represent a number was visited before. If the current value was visited, i.e. index Math.abs(nums[i])-1, the result will add this value. As 1 ≤ a[i] ≤ n (n = size of array).


  • 1

    Another O(n) approach without negating

    public List<Integer> findDuplicates(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            // put nums[i] to it's right place if the right place is not already nums[i]
            while(i != nums[i]-1 && nums[i] != nums[nums[i]-1]) { 
                int temp = nums[i];
                nums[i] = nums[nums[i]-1];
                nums[temp-1] = temp;
            }
        }
        List<Integer> result = new ArrayList<Integer>();
        for(int i = 0; i < nums.length; i++) {
            if(i != nums[i]-1) result.add(nums[i]);
        }
        return result;
    }

  • 0
    This post is deleted!

Log in to reply
 

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