Using bit operators to solve this problem with O(1) space and O(n) time


  • 0
    J

    The idea is to construct an all-1 bit num has the same bit length with the input nums, for example: nums = [3,4,-1,1] for '0b1111'.

    In the for loop of nums, using each positive num to mask the all-1 bit num, which means to modify the corresponding position of all-1 bit num from 1 to 0, for example, when num is "3", the all-1 bit num will be modified to '0b1101'.

    Then just count the bit length to get the first missing positive integer.

    class Solution(object):
        def firstMissingPositive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            len_nums = len(nums)
            
            missing_mask = (2**len_nums) - 1
            for num in nums:
                if 0 < num <= len_nums:
                    missing_mask = missing_mask & ~(1<<(len_nums - num))
            missing_mask_len = missing_mask.bit_length()
            
            if missing_mask_len == 0:
                return len_nums + 1
            missing_num = len_nums - missing_mask_len + 1
            
            return missing_num
    

Log in to reply
 

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