Missing Positive Integer


  • 1
    R

    Algo:

    1. Separate all positive numbers to the right and move forward to the problem.
    2. Find the missing positive the positive elements by :
      • Mark arr[i] as visited by making arr[arr[i] - 1] negative.
        ... - Return the first index value at which is positive

    /* swap two integers */
    void swap(int *a, int *b)
    {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
    }

    /* puts all non-positive (0 and negative) numbers on left
    side of arr[] and return count of such numbers */
    int separateNP(int arr[], int size)
    {
    int j = 0, i;
    for(i = 0; i < size; i++)
    {
    if (arr[i] <= 0)
    {
    swap(&arr[i], &arr[j]);
    j++; // increment count of non-positive integers
    }
    }

    return j;
    

    }

    int getMissing(int arr[], int size)
    {
    int i;

    // Mark arr[i] as visited by making arr[arr[i] - 1] negative. Note that
    // 1 is subtracted because index start from 0 and positive numbers start from 1
    for(i = 0; i < size; i++)
    {
    if(abs(arr[i]) - 1 < size && arr[abs(arr[i]) - 1] > 0)
    arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];
    }

    // Return the first index value at which is positive
    for(i = 0; i < size; i++)
    if (arr[i] > 0)
    return i+1; // 1 is added becuase indexes start from 0

    return size+1;
    }

    int firstMissingPositive(int* nums, int numsSize) {
    // First separate positive and negative numbers
    int shift = separateNP (nums,numsSize );

    // Shift the array and call findMissingPositive for
    // positive part
    return getMissing(nums+shift, numsSize-shift);
    }
    ...


  • 0
    N

    Python3 solution

    Algo:

    • convert the list into a set(finding an element in set is O(1))
    • iterate from 1 to (1+"length of nums"+1) and first number we can't find is the answer

    Why (1+"length of nums"+1):

    • we are to find first missing positive number(which start from 1)
    • if "nums" start with 1: maximum value it can go to is 1+"length of nums"
    • all other cases, we will for sure find missing number before: 1+"length of nums" value
    class Solution:
        def firstMissingPositive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums) == 0:
                return 1
    
            nums = set(nums)
            
            for i in range(1, 1+len(nums)+1):
                if i not in nums:
                    return i
    

  • 0
    R

    @nitinsurya finding a number in a set is O(n) operation in worst case, only in average case it is O(1) depending on the input size and hash table size which implements this set.


Log in to reply
 

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