Find the Missing Number

Another week has passed so let’s discuss a new algorithm. For this problem, we want to find a missing number inside of an array. The number we want is the smallest possible positive integer that is missing inside of the array. For example, let’s look at an array

var A = [1, 3, 6, 4, 1, 2]. 

When we sort it, the array is

[1,1,2,3,4,6],

and we can see the missing link is 5. Let’s look at another array

[1,2,3].

We want the answer to return 4. And finally, for this array

[-3, -1],

we want to return 1.

The problem asks we write an efficient algorithm that will solve this problem. The first approach to getting there is doing it by brute force. What we want to do is start from 1 to the array length plus 1. If the number x does not exist inside of the array, return the first positive number. The code is simply

function missingNumber(arr){
    for(var x = 1; x <= arr.length + 1; x++){
         if(arr.indexOf(x) === -1){
             return x
         }
    }
}. 

It looks simple, but the problem is that the time complexity is O(n²). We want O(n). Now what can we do to make the problem more efficient? Let’s start by looking at our if-statement. The if statement is evaluating if x exists in the array so it behaves like another for loop.

To avoid the if statement acting like a for loop, let’s start by announcing a new variable

var min = 1

because we don’t want to go less than 1. Next, we sort the array

arr.sort(function(a, b){return a- b}). 

Then we go through the array arr and if the condition

arr[x] === min

is met, we add to min

min ++. 

Full code is

function solution(A) {         
      var min = 1     
      A.sort(function(a, b){return a - b})      
      for(var x = 0; x < A.length; x++){         
           if(  A[x] === min){             
                min++         
           }     
      }     
      return min 
}. 

The time complexity of this code is O(n) or O(n * log(n)).