def findDisappearedNumbers(self, nums): """ :type nums: List[int] :rtype: List[int] """ n = len(nums) i = 0 while i < n: # until nums[i] is in it's correct place # nums[i]'s correct place is nums [ nums[i] - 1 ] ( place of 1 is index 0, place of 2 is index 1 and so on) while nums[ nums[i] - 1 ] != nums[i] : x = nums[ nums[i] - 1 ] nums[ nums[i] - 1 ] = nums[i] nums[i] = x # nums[i] has been put in its place i += 1 missing =  for i in range(n): if nums[i] != i+1: # expecting i+1 at ith place in nums! Didn't find it? i+1 is missing! missing.append(i+1) return missing
O(n) amortized in python with comments
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.