Find Numbers Disappeared in Array
- 1 min read
- LC-Easy
3 years ago
Solution
- Use the actual array itself to store whether or not a number was seen
- Loop through each number
num.num - 1is the index which we will mark as negative. - Remember that
nummight be negative due to a previous marking- so always take the absolute value first, then decrement by 1. - Use this index to set
nums[idx]as negative. - Then, go through the array one more time and check which indices have positive values- these are the ones which do not exist in the array, more specifically,
i + 1does not exist in the array. Add this to the answer.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
idx = abs(nums[i]) - 1
nums[idx] = -abs(nums[idx])
ans = []
for i in range(len(nums)):
if nums[i] > 0:
ans.append(i + 1)
return ans