Simple Java solution O(N) time O(1) space


  • 0
    K
    public class Solution {
        public List<Integer> findDuplicates(int[] nums) {
            List<Integer> duplicates = new LinkedList<Integer>();
            // If a number has been seen we will set its corresponding index to its negative
            // If it is already negative then we have seen it once
            for (int i = 0; i < nums.length; i++) {
                int val = Math.abs(nums[i]);
                if (nums[val-1] < 0)
                    duplicates.add(val);
                else
                    // We are setting the value at this index to be negative to imply we've seen the index itself in the array already
                    nums[val-1] = -1 * nums[val-1]; 
            }
            return duplicates;
        }
    }
    

Log in to reply
 

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