[Leetcode]442. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?

The straightforward approaches include implementing a hashset or using bucket sort, with O(n) time complexity and O(n) space complexity. With one trick, however, we would be able to achieve O(1) space complexity.

We can use the items a[i] as the index, and make a[i] negative to indicate that we have visited it once. Following this manner, we would be able to detect items that we’ve seen.

Code

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        ret = []
        for i in range(len(nums)):
            if nums[abs(nums[i])-1] < 0:
                ret.append(abs(nums[i]))
            else:
                nums[abs(nums[i])-1] *= -1
        return ret
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments