Find missing positive number
Given a list of integers we like to find the smallest missing integer number.
Examples:
{1,2,5,8,9,4} Ans = 3
{ 3, 4, -1, 1 } Ans = 2
{8,10,7,9,4} Ans = 1
Solution:
We want to throw all numbers to the hashset
We then iterate from num = 1 and keep checking if the hashset contains num and if it is true, we will keep increment num by 1 until we no longer find the number in the hashset. When we do, then num will be the answer.
We need to also handle extreme cases like if all elements are negative number, then we just return 1.
public static int FirstMissingPositive(int[] A) {
if (A.Length == 0)
return 0;
if (A.Max() <= 0)
return 1;
int n = A.Length;
HashSet<int> hs = new HashSet<int>();
for (int i = 0; i < n; i++) {
if (!hs.Contains(A[i]))
hs.Add(A[i]);
}
int num = 1;
while (hs.Contains(num)) {
num++;
}
return num;
}