C# solution


  • 0
    Z

    The key to this problem is to recognize that the solution must fall in the range of 1 (the smallest positive integer) and n + 1 (in the case where every value from 1 to n lives in the array)

    First, the function places every value that falls in this range in its correct slot. For example, the value 1 is placed in the first slot (index 0).

    It then scans the array and finds the first slot that doesn't match the value placed there, and returns the value it should have found. If this fails to return, then we have the case where everything from 1 to n is represented, and it returns the largest possible value.

    public class Solution {
        public int FirstMissingPositive(int[] nums) {
            for (int i = 0; i < nums.Length; i++)
            {
                //We only care about current values that are in range and are not already correctly placed
                while (nums[i] >= 1 && nums[i] < nums.Length + 1 && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1])
                {
                    Swap(ref nums[i], ref nums[nums[i] - 1]);
                }
            }
            
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] != i + 1) return i + 1;
            }
            return nums.Length + 1;
        }
        private void Swap(ref int a, ref int b)
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
    }
    

Log in to reply
 

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