Python solution with detailed explanation


  • 0
    G

    Solution

    Find All Duplicates in an Array https://leetcode.com/problems/find-all-duplicates-in-an-array/

    • The elements are between1 and N and N is the size of the array. Therefore we can implicitly map an element to an index i.e. 1 maps to index 0, 2 maps to index 1, ...N maps to index N-1
    • Say for example that the number 4 appears twice. 4 implies index 3. We know that there are no negative numbers in the array. How about I mark the number at index 3 as negative when I first encounter 4. Now at the next occurence of 4, I will find the position implied by it (i.e. number at index 3) as negative. This means that 4 is a duplicate!
    • Make sure you use the abs(x)-1 to select the index implied by x. That is because, in a previous iteration, the position of x might have been marked negative.
    class Solution(object):
        def findDuplicates(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            result = []
            for x in nums:
                if nums[abs(x)-1] < 0:
                    result.append(abs(x))
                else:
                    nums[abs(x)-1] = -1*nums[abs(x)-1]
            return result
    

Log in to reply
 

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