public class Solution {
    public int FirstMissingPositive(int[] nums)
    {
        // If empty array , 1 should be answer
        if (nums == null || nums.Length == 0)
            return 1;

        // Set all -ve # to 0 , since -ve # are not of our interest & 0 is neutral #
        for(int i= 0; i<nums.Length; i++)
        {
            if(nums[i] < 0)
            {
                nums[i] = 0;
            }
        }
        // Now we don't have -ve # anymore in array
        // Iterate through array & as positive # (num) is seen, make Index = (num-1) make 
        // This info will be used later to determine if any given # exist in array or not. 
        for(int i= 0; i<nums.Length; i++)
        {
            // Since we are modfying array & val can be -ve, making sure we pick Abs value
            int val = Math.Abs(nums[i]);
            
           // If its 0 or > array size, Ignore
           if(val <= 0 || val > nums.Length)
           {
               continue;
           }
            
           // Else if something is +ve, make its arr[index-1] -ve. If its already -ve, don't change anything
           if(nums[val-1] > 0)
           {
               nums[val-1] *= -1;
           }
            // Special case, it 0 is seen, set it to array length+1
            else if(nums[val-1] == 0)
            {
                nums[val-1] = -1* (nums.Length+1);
            }

        }

        // Finally return 1st index, where positive value is seen
        for(int i= 1; i<=nums.Length; i++)
        {
            if(nums[i-1] >= 0)
            {
                return i;
            }
        }
        
        // If all values are negative, answer will be arr length + 1
        return nums.Length+1;
    }
}