Solution by indicating the presence of a number between 1 to n in an array


  • 0
    S
    
    class Solution {
        public int firstMissingPositive(int[] nums) {
            int idx=0;
            if(nums==null|| nums.length==0)
                return 1;
            /*Zero is an irrelevant number, so we convert it to negative */
            for(int i=0;i<nums.length;i++)
                if(nums[i]==0)
                    nums[i]=-1;
            /*Make a demarkation for all positive integers in the array */
            for(int i=0;i<nums.length;i++)
            {
                if(nums[i]<0)
                {
                    int tmp=nums[idx];
                    nums[idx]=nums[i];
                    nums[i]=tmp;idx++;
                }
                
            }
            /*Mark that the positive number is present by reversing the sign on the number present at its index */
            for(int i=idx;i<nums.length;i++)
            {
                if(Math.abs(nums[i])<=nums.length)
                {
                    if(Math.abs(nums[i])-1<idx)
                        nums[Math.abs(nums[i])-1]=Math.abs(nums[Math.abs(nums[i])-1]);
                    else
                       nums[Math.abs(nums[i])-1]=-Math.abs(nums[Math.abs(nums[i])-1]); 
                }   
            }
            /*If the number is between 1 to n, the number present at its index is greater than 0, if it is less than idx, else it is less than
            zero, if it is greater than idx. If all elements less than idx have positive sign and that greater than idx have negative sign, it means
            that all numbers from 1 to n are present, so the number is n+1*/
            for(int i=0;i<nums.length;i++)
            {
                if(i<idx && nums[i]<0)
                    return i+1;
                if(i>=idx && nums[i]>=0)
                    return i+1;
            }
            return nums.length+1;
        }
    }
    

Log in to reply
 

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