You are given an unsorted array of unsigned integers. How will you find the smallest non negative integer that is not in the list?
Let us assume the input array is non negative. Since the input array can have duplicates there can be one or more than one element greater than the size of the input array. So there must be at least one element in between 0 and n-1 that is missing in the input array where n is the size of the input array. Hence, we can ignore the elements that are greater or equal to n . The algorithm works as :
Time complexity = \( O(n) \), space complexity = \( O(1) \). public int findSmallestElemNotInAnArray(int[] array){ |