Java Simple Solution


  • 130
    Y
    public class Solution {
        // when find a number i, flip the number at position i-1 to negative. 
        // if the number at position i-1 is already negative, i is the number that occurs twice.
        
        public List<Integer> findDuplicates(int[] nums) {
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < nums.length; ++i) {
                int index = Math.abs(nums[i])-1;
                if (nums[index] < 0)
                    res.add(Math.abs(index+1));
                nums[index] = -nums[index];
            }
            return res;
        }
    }
    

  • 0
    P

    Thank you for your solution. Very tricky!


  • 6
    Y

    @PENETRATIVE

    Thank you!

    I was thinking we need a way to "hash" the same number together without using extra space. I am inspired by the range of the input value (1 - N), which seems fit the index of the input array (0 - N-1).

    If I hash num[i] to index num[i]-1, then I need to store it at index num[i]-1 smartly. I shouldn't make irrecoverable change to the element at that position, because I may need the element in the future. Again using the given range of input is (1 - N), if flip it to the opposite I can still recover it using Math.abs


  • 1

    great solution, very clever. But I always hesitate when the solution involves modifying the input array. Generally is this an okay thing to do? Thoughts? Thanks.


  • 0
    M

    wow, what a tricky solution. GOOD JOB, BTW, do I know you?


  • 8
    Y

    @jdrogin

    Hello! I think it will be a good question to ask interviewer during the interview. In this solution, we can recover the original input array by doing Math.abs for all the elements before the function return.


  • 0

    @YuxinCao excellent point. I'm convinced!


  • 2
    T

    Just wondering how this works.
    For e.g. you are picking a value from array and you go to the point in array till this value to mark is negative.

    For e.g., if you have array [2, 5, 88, 123, 3455]; then how come nums[index] will not give ArrayOutBound exception ???
    int index = Math.abs(nums[i])-1;
    if (nums[index] < 0)


  • 2

    the numbers in the array, x, are between 0 and n (the length of the array)
    0 <= x < n

    so you will not have a number like 3000 in an array of length 4.


  • 1
    A

    @TechPrep Don't forget there is a assumption: "1 ≤ a[i] ≤ n (n = size of array)", there will not give ArrayOutBound exception


  • 0
    J

    @TechPrep please read the restrictions, ok? Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.


  • 8
    J

    we can optimize the code a little bit. Because index can never be negative, we don't have to use Math.abs(index + 1)

    if (nums[index] < 0)
        res.add(index+1);
    

  • -1
    W

    @Michael_Facebooker Son, Dad miss you.


  • 0

    @TechPrep : Problem statement : Given an array of integers, 1 ≤ a[i] ≤ n


  • 1
    A

    I was just wondering if we have something like {{4,3,2,2,2,2,3,1}}. In that case, this returns the answer to be [2,2,3]. But from my understanding, the output should be [3] only as it is the only element that appears twice. Or is it okay to assume this is correct because the question does not specify exactly twice.


  • 1
    S

    @aritra90tnp "some elements appear twice and others appear once"


  • 0
    A

    @sentimental Thanks for pointing that out. I missed that.


  • 0
    Z

    good solution


  • 3
    S
     res.add(Math.abs(index+1));
    

    Here you don't have to get absolute value since index + 1 will never be < 0


  • 0
    J

    if (nums[index] < 0)
    res.add(Math.abs(index+1));

    since index is always positive, I do not think the code Math.abs(index + 1) is really necessary, I tried with res.add(index + 1), it passed.

    But this is really tricky and great idea!


Log in to reply
 

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