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

  • 0

    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
            return posInt

  • 0

    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.