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?
Example:
Input: [4,3,2,7,8,2,3,1] Output: [2,3]
Description taken from https://leetcode.com/problems/find-all-duplicates-in-an-array/.
#O(N) Time, O(1) Spaceclass Solution: def findDuplicates(self, nums: List[int]) -> List[int]: result = [] for num in nums: if nums[abs(num)-1] < 0: result.append(abs(num)) else: nums[abs(num)-1] *= -1 return resultTo solve this question, a few approaches may come to mind right away.
We could sort the list and check for neighboring duplicates. We could also store each number in a dictionary and the number's value in the dictionary whenever we saw it again.
Let's note that the description states that the input values will range from one to the size of the array. Whenever we see that line, that gives us a hint. If the values range from one to n, then we can use each index as a mapper instead of requiring external memory.
This problem can be solved optimally by traversing the input array and for each number we see, we will set the corresponding numbered index to negative. By doing this, if we have a duplicate number then we would access the index a second time and see that we have an element that was changed to negative already which would mean that we visited the same number twice.
Let's start by initializing our result array.
result = []
We will then step through each number within the input array and see if the element in the corresponding numbered index is negative.
We'll need to subtract one from the index value because array indexing starts at zero. We'll also need to take the absolute value in case the number has been set to negative previously so we wouldn't flip it back to positive and make this algorithm useless.
for num in nums: if nums[abs(num)-1] < 0:
If the element within the index is negative, we know this is our second time accessing this element and it is a duplicate. We can then append the current number to the output, taking the absolute value in case it was changed to negative.
result.append(abs(num))
If the element within the index is not negative, we will make it negative in case we access it again.
else: nums[abs(num)-1] *= -1
Once we have finished traversing the array and have appended all of our duplicates to the result, we will return the result.
return result