# O(n) time, O(1) space Python solution with explaination

• Input:
[4,3,2,7,8,2,3,1]

sort, get [1,2,2,3,3,4,7,8]

then the solution takes two rounds of n elements, for the first round, we'll put every elements we met into place it belongs. For those numbers who is not in the expected position, we'll use -1 to hold the place. Along with 'i' increasing, some of the -1s will be replaced by this line: nums[nums[i] - 1] = nums[i]. So at the end of the first round, those who disappeared will keep -1s.

second round to collect the placeholders

``````class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if len(nums) < 2:
return []
nums.sort()    #[1,2,2,3,3,4,7,8]
result = []
for i in range(len(nums)):
#find the position of nums[i] #
nums[nums[i] - 1] = nums[i]
if nums[i] != i + 1:
nums[i] = -1

#now the nums looks like [1,2,3,4,-1,-1,7,8]

for j in range(len(nums)):
if nums[j] == -1:
result.append(j + 1)
return result
``````

• Sorting itself is O(nlogn), so your solution is not O(n) in time.

• That's true, thanks for pointing out! How about this, without sorting, I'll just go as far as I could to re-arrange the numbers for each 'i'.

[4,3,2,7,8,2,3,1]

[-1,3,2,4,8,2,3,1] temp = 7

[-1,3,2,4,8,2,7,1] temp = 3

...

[-1,2,3,4,8,2,7,1] after first while loop

...

[1,2,3,4,-1,-1,7,8]

then get result based on -1s

``````class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if len(nums) < 2:
return []
result = []
for i in range(len(nums)):
if nums[i] != i + 1:
temp = nums[i]
nums[i] = -1
while nums[temp - 1] != temp and temp != -1:
t = nums[temp - 1]
nums[temp - 1] = temp
temp = t

for j in range(len(nums)):
if nums[j] == -1:
result.append(j + 1)
return result
``````

• @samk522 we can use O(n) sort for this case since elements are from 1 to n

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