this is the original question
https://www.geeksforgeeks.org/find-the-smallest-positive-number-missing-from-an-unsorted-array/
You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space. You can modify the original array.
Input: {2, 3, 7, 6, 8, -1, -10, 15} Output: 1
Input: { 2, 3, -7, 6, 8, 1, -10, 15 } Output: 4
Input: {1, 1, 0, -1, -2} Output: 2
using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace ArrayQuestions
{
[TestClass]
public class FindTheSmallestNonnegativeNumberNoyInArray
{
[TestMethod]
public void FindTheSmallestNonnegativeNumberNoyInArrayTest()
{
int[] array = {2, 3, 7, 6, 8, -1, -10, 15};
int result = FindSmallestPositiveHash(array);
int expected = 1;
Assert.AreEqual(expected, result);
}
[TestMethod]
public void FindTheSmallestNonnegativeNumberNoyInArrayTest2()
{
int[] array = { 2, 3, -7, 6, 8, 1, -10, 15 };
int result = FindSmallestPositiveHash(array);
int expected = 4;
Assert.AreEqual(expected, result);
}
private int FindSmallestPositiveHash(int[] array)
{
HashSet<int> set = new HashSet<int>();
int maxPositive = 0;
for (int i = 0; i < array.Length; i++)
{
if (!set.Contains(array[i]))
{
maxPositive = Math.Max(maxPositive, array[i]);
set.Add(array[i]);
}
}
for (int i = 1; i < maxPositive; i++)
{
if (!set.Contains(i))
{
return i;
}
}
return maxPositive + 1;
}
}
}
I know there is a better solution, I tried to implement the hash based solution please comment or runtime and performance. Thanks