Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input: [4,3,2,7,8,2,3,1] Output: [5,6]
The description was taken from https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/.
#O(N) Time, O(1) Spaceclass Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: result = [] for num in nums: if nums[abs(num) -1] > 0: nums[abs(num) -1] *= -1 for i in range(0, len(nums)): if nums[i] > 0: result.append(i + 1) return resultTo solve this question, the first approach that may come to mind is to store each number in a dictionary and then traverse the input array, marking each dictionary key as seen before returning the missing values that weren't seen.
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.
We can solve this problem optimally by traversing the input array and for each number we see, we will set the corresponding numbered index to negative. By doing this, we can traverse the input array a second time and return the index of any element that wasn't flipped to negative, meaning that we never saw it in our first traversal.
Let's start by initializing our result array.
result = []
Next, we will then step through each number within the input array and flip the element in each corresponding numbered index to be 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: nums[abs(num) -1] *= -1
After we have set negative elements for every number we have seen, we will traverse the array once more.
for i in range(0, len(nums)):
If we encounter an element with a positive value, it means we never visited the corresponding index. For example, if the element at index four is positive, it means we never saw four.
If this is the case, we will append the current index to the result list since that will give us the disappeared corresponding number.
We'll need to add one when we append the index because array indexing starts at zero.
if nums[i] > 0: result.append(i + 1)
Once we have traversed the array a second time and appended each missing value, we will return the result.
return result