Algorithms for Coding Interviews in Java/

...

/

Solution: Missing Number in Sorted Array

Solution: Missing Number in Sorted Array

This review discusses the solution of the missing number in a sorted array challenge in detail.

We'll cover the following...

Solution #1

Press + to interact
class MissingNumber {
 public static int missingNumber(int[] arr, int size) {
  int missing = -1; // if no element is missing
  int last = arr[0]; // start off from the first element
  if(last != 1)
  {
      return 1;
  }
  for (int i = 1; i < size; i++) { // traverse through the whole array
   if (arr[i] - last > 1) {
    missing = last + 1;
    break;
   }
   last++;
  }
  return missing;
 }
 public static void main(String args[]) {
  int[] input1 = {1,2,4};
  System.out.println(missingNumber(input1, input1.length));
 }
}

A naive solution to this problem would be:

  1. Traverse through the whole list starting from the first index.

  2. Find out the difference between the current and the last index element.

  3. If the difference is greater than 1, it means the integer between the current and last index is missing.

  4. Return index+1 (as the array is contiguous and starts from 1, the missing number will be equal to index+1).

Time complexity

This solution iterates through every single element and takes the same approach as finding an element in an unsorted array. It makes no use of the fact that the array has contiguous and sorted elements. Therefore, the time complexity of this method is ...