Find the smallest element not in an array
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (2402)

You are given an unsorted array of unsigned integers. How will you find the smallest non negative integer that is not in the list?


Posted Answers

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 :


  • Iteration 1 : Iterate through the input array and write the value at the index to the index of the value recursively. Ignore all elements greater than n .
  • Iteration 2 : Iterate through the input array once again to check whether there is a mismatch between the index and its value.
  • If mismatch occurs, return the index.
  • If not, return n .

Time complexity = \( O(n) \), space complexity = \( O(1) \).

public int findSmallestElemNotInAnArray(int[] array){

/* Size of the array */
int n = array.size;

/* Iteration 1 */
for (int i = 0; i < n; i++){
currentValue = array[i];
while(currentValue < n & & currentValue != array[currentValue]){
nextValue = array[currentValue];
array[currentValue] = currentValue;
currentValue = nextValue;
}
}

/* Iteration 2 */
for (int i = 0; i < n; i++){
if array[i] != i:
return i;
/* Since we are looking for the smallest element */
break;
}

/* Otherwise */
return n;

}

You need to Sign In to post your solution.