Search

First Missing Positive

Updated: Mar 24, 2021

Given an unsorted integer array nums, find the smallest missing positive integer.


Example 1:

Input: nums = [1,2,0]
Output: 3

Example 2:

Input: nums = [3,4,-1,1]
Output: 2

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

Constraints:

  • 0 <= nums.length <= 300

  • -231 <= nums[i] <= 231 - 1

Follow up: Could you implement an algorithm that runs in O(n) time and uses constant extra space?


Solution:

class Solution {
   public int firstMissingPositive(int[] nums) {
    if(nums.length==0) return 1;
    int lastPositiveindex=partition(nums)+1;
           
    for(int i=0;i<lastPositiveindex;i++){
       int k=Math.abs(nums[i]);
        if(k<=lastPositiveindex)
            nums[k-1]=(nums[k-1]<0)?nums[k-1]:-nums[k-1];
    }
    for(int i=0;i<lastPositiveindex;i++){
        if(nums[i]>0){
            return i+1;
        }
    }
    return lastPositiveindex+1;
}

public int partition(int[] nums)
{
    int j=-1;
    for(int i=0;i<nums.length;i++){
        if(nums[i]>0){
            j++;
            int temp = nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }
    }
    return j;
}
}


6 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.