Python O(n), O(1) space using swapping to partially sort the list.


  • 0
    C
    class Solution(object):
        def findDisappearedNumbers(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            for i in range(len(nums)):
                # The while loop should execute a maximum of n times total since each execution puts an element in its correct sorted position.
                while nums[i] != (i + 1) and nums[i] != nums[nums[i] - 1]:
                    j = nums[i]
                    nums[i], nums[j - 1] = nums[j - 1], nums[i]
            
            result = []
            for i in range(len(nums)):
                if nums[i] != i + 1:
                    result.append(i + 1)
            return result
    

Log in to reply
 

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