C++ beats 98%


  • 10
    F
    vector<int> findDuplicates(vector<int>& nums) {
            vector<int> res;
            for(int i = 0; i < nums.size(); i ++){
                nums[abs(nums[i])-1] = -nums[abs(nums[i])-1];
                if(nums[abs(nums[i])-1] > 0) res.push_back(abs(nums [i]));
            }
            return res;
        }
    

    Same mark by negation as a lot of people use, if you ever come across a value that is positive after negating if you know you've seen it before!


  • 0
    A

    @ffffffffffffff
    can you explain what this code do exactly. thanks
    nums[abs(nums[i])-1] = -nums[abs(nums[i])-1];
    if(nums[abs(nums[i])-1] > 0) res.push_back(abs(nums [i]));


  • 1
    F

    @AminC

    nums[abs(nums[i])-1] = -nums[abs(nums[i])-1];
    if(nums[abs(nums[i])-1] > 0) res.push_back(abs(nums [i]));
    

    Imagine going through the list and finding a 5 somewhere random (let's say at index 1). What the first line says is go to index "5" (whatever may be there) and make it negative whatever the current value is (say a 1 sits there, make it -1). Now say we come across another 5 at index 3, we again go to index 5 and make it negative. Now the 1 that is at index 5 is now positive, and when we check we'll know we've visited this value twice. That means whatever value we're at in our loop is the duplicated value.


  • 0
    A

    @ffffffffffffff
    I understand this but why we don't iterate through the vector one by one rather than chosing random numbers also why you [abs(nums[i])-1] use -1 here, also is there is any link can you provide so i can read further about it?
    Thanks for your time.


  • 0
    F

    @AminC

    This solution is very similar to https://discuss.leetcode.com/topic/64805/java-easy-to-understand-solution-without-extra-space-and-in-o-n-time

    the -1 is because the values are stored in 1 ... N, arrays use index 0 as a starting point, so this will shift every index by 1. If the -1 wasn't there it is possible to access values that don't exist in your array.


  • 0
    A

    Oh I see make sense, does this algorithm work if we chose to loop starting from 0 to n-1 rather than just using the array values? also what happen if the values of the array are greater than N value for example if we had vector of {1,2,3,90,200,200} would it still catch that? cause based what I see here it don't.


  • 0
    F

    @AminC

    I'm not sure what you mean by 0 to n-1, isn't that what's happening already in the for loop? Make sure you understand this constraint 1 ≤ a[i] ≤ n (n = size of array). Imagine trying to access array[array.size()], it wouldn't work because the size is one larger than the last element because we start at index 0 in c++. Since the constraint can contain values up to the size, we have to downshift by one.

    If you want to take advantage of indices as to not have any other data structure than you must shift this constraint by one i.e. 1-1 ≤ a[i]-1 ≤ n-1 => 0 ≤ a[i]-1 ≤ n-1.

    For your second question, it will not work if there are random values, this is designed to work for the constraint 1 ≤ a[i] ≤ n, although there are other solutions involving XOR that will work for any constraint.


  • 1
    A

    @ffffffffffffff
    Sorry typo I meant 1 to n-1, ma bad. I don't wanna dive into XOR right know cause it's little bit complex and need some prior understanding of binary representation if you know what I mean lol, thanks for your time!


  • 0
    F

    @AminC

    For this problem I prefer negation because it's more intuitive for me, but there are similar problems on leetcode where XOR is more necessary.

    and no problem, hope some of that made sense.


  • 0
    A

    okay then, good luck solving. I'm gonna bust my ass solving some string manipulation on hackerrank,


  • 1
    S

    Great use of common sense !


  • 0
    P

    nice solution!


Log in to reply
 

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