O(n) amortized in python with comments


  • 1
    S
        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

Log in to reply
 

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