O(n) time , O(1) space, C code


  • -5
    P
    int firstMissingPositive(int* nums, int numsSize) {
            //put number in its right place, E.g 1 should be in nums[0], 2 in nums[1], so on..
            for (int i = 0; i < numsSize; i++) {
                while ((nums[i] > 0) && (nums[i] <= numsSize) && (nums[i] != nums[nums[i] - 1])) {
                    swap(&nums[i], &nums[nums[i] - 1]);
                }
            }
            
            //find missing number
            for (int i = 0; i < numsSize; i++) {
                if (nums[i] != i + 1) return i+1;
            }
            
            return numsSize + 1;
        }

Log in to reply
 

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