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

  • 0
    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)
                    // 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.