First Missing Positive, super simple Python solution (52 ms), but is it constant space?


  • 0
    J

    I made this quick solution to the problem and it gets accepted, but is it constant space? I'm unfamiliar with the technicalities of that term.

    class Solution(object):
        def firstMissingPositive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            posInt = 1
            
            while posInt <= len(nums):
                
                if posInt in nums:
                    posInt += 1
                else:
                    break
            
            return posInt
    

  • 0
    E

    It's constant space but your code is not a O(n), but a O(n^2) solution. You're looping through the entire array to look for each positive number, starting from 1, then returning the value that is missing. You're doing a O(n) lookup for n elements: O(n^2) time complexity.


Log in to reply
 

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