# C# solution: bucket sort

• Even if there is "while" in the loop, the time complexity is no more than 2n.

I changed number to index at the beginning. So I do not need to do the transformation when I check the index.

For example: inputs: [3, 4, -1, 1]

// change to the index
[2, 3, -2, 0]

// start to compare with the index
[-2, 3, 2, 0] (i = 0)
[-2, 0, 2, 3] (i = 1)
[0, -2, 2, 3] (i = 1)
[0, -2, 2, 3] (i = 2)
[0, -2, 2, 3] (i = 3)

// find the first item which does not equal to the index
find out -2 (i = 1)

return i + 1 = 1 + 1 = 2

``````public class Solution
{
public int FirstMissingPositive(int[] nums)
{
for (int i = 0; i < nums.Length; i++)
{
// Change the number to the index.
nums[i]--;
}

for (int i = 0; i < nums.Length; i++)
{
while(0 <= nums[i] && nums[i] < nums.Length && i != nums[i])
{
// Be careful! If we do not check, it may cause the infinite loop.
if (nums[nums[i]] == nums[i]) break;

var temp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = temp;
}
}

for (int i = 0; i < nums.Length; i++)
{
// Find the first item which does not equal to the index.
if (nums[i] != i)
{
return i + 1;
}
}

return nums.Length + 1;
}
}
``````

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