6 line C++ O(n) code and no extra space


  • 0
    A

    We can use the positions to mark whether an integer is present or not.

        int findDuplicate(vector<int>& nums) {
            for(auto num : nums){
                if(nums[abs(num)-1] < 0){
                    return abs(num);
                }
                nums[abs(num)-1] *= -1;
            }
        }
    

Log in to reply
 

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