C++ 12ms solution with simple explanation


  • -8
    A

    class Solution {
    public:
    int findDuplicate(vector<int>& nums) {

        if(!nums.size())
            return -1;
        
        // Here we will use a marking strategy to identify the duplicate
        // Specifically we will mark the number at the array position of 
        // a visited item as -ve (e.g we will mark nums[2] as -nums[2] 
        // when we encounter a 2 while iterating over the array elements)
        // Then if we ever encounter the same number again and the value
        // at that position (say 2 as in the above example) in the array is -ve - we know its a duiplicate.
        // This is guaranteed by the fact that all numbers are between 1 and n (i.e nothing is -ve in the begining)
        // and that there is only 1 duplicate (which is why we can bail out as soon as we find one and not have to save anything
        // there by meeting the requirements in the question. 
         
        
        for(int i=0;i<nums.size();++i)
        {
            
            // Computing the absolute value once reduce runtime from  >20ms to 12ms 
            int absoluteValueAtNumsIthPosition = std::abs(nums[i]);
            
            if(nums[absoluteValueAtNumsIthPosition ] > 0)
                nums[absoluteValueAtNumsIthPosition ] = -nums[absoluteValueAtNumsIthPosition ];
            else
                return absoluteValueAtNumsIthPosition ;
        }
        
    }
    

    };


  • 0
    A

    Anyone voting down on this solution - can you please add a line of comment as to why you are voting down ?


  • 0
    A

    I haven't voted it down however I believe that the main problem is that you are changing the array whereas it clearly states not to do so. Goodluck!


Log in to reply
 

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