Missing Number

Problem

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

For example:

Input: [4, 0, 3, 1]
Output: 2

Input: [8, 3, 5, 2, 4, 6, 0, 1]
Output: 7

Solution

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        #1) sort the numbers in the correct position by their index
        #2) find the missing number that is not equal to it's index
        
        i=0
        while i < len(nums):
            j = nums[i] #getting the index that this number should be in
            if nums[i] < len(nums) and nums[j] != nums[i]:
                nums[j],nums[i] = nums[i],nums[j]
            else:
                i+=1
                
        for i in range(len(nums)):
            if i != nums[i]:
                return i
        return i+1
        
        
        
#Since the array has numbers in range [0, n], there
#will possibly exist a num[n] but not an index n so
#we skip this

#Time: O(n)
#Space: O(n)