Simple C# solution with proper explanation


  • 0
    *

    public class Solution {
    public int FirstMissingPositive(int[] nums) {

    	int negativeNumCount = 0;
    
    	// Segregate negative(and zeros) and positive integers; put all negative integers at the end of the array;	
    	for(int i =0; i<nums.Length-negativeNumCount; i++)
    	{
    		if(nums[i]<=0)
    		{
    		  	negativeNumCount = negativeNumCount + 1;
    			negativeNumCount = PushNegativeNumToEndOfArray(nums, i, negativeNumCount);
    		}
    	}
    
    	// Negate all the positive numbers if it exists;
    	for(int i =0; i<nums.Length-negativeNumCount; i++)
    	{
    		if(nums[i] <= nums.Length-negativeNumCount)
    			nums[Math.Abs(nums[i])-1] = - Math.Abs(nums[Math.Abs(nums[i])-1]);
    	}
    	
    	for(int i =0; i<nums.Length-negativeNumCount; i++)
    	{
    		if(nums[i] > 0)
    			return i+1;
    	}
    		
    	return nums.Length-negativeNumCount+1;
    }
    
    
    private int PushNegativeNumToEndOfArray(int[] nums, int index, int negativeNumCount)
    {
    	while(nums[nums.Length - negativeNumCount] <= 0 && index < (nums.Length - negativeNumCount))
    	  	negativeNumCount = negativeNumCount + 1;
    	
    	nums = swap(nums, index, nums.Length - negativeNumCount);
    	
    	return negativeNumCount;
    }
    
    
    private int[] swap(int[] nums, int a, int b)
    {
    	int temp = nums[a];
    	nums[a] = nums[b];
    	nums[b] = temp;
    	
    	return nums;
    }
    

    }


Log in to reply
 

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