Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Missing Number in Sorted Array

Explore how to solve the missing number problem in a sorted array efficiently by applying divide and conquer strategies similar to binary search. Understand the step-by-step process, boundary cases, and achieve a time complexity of O(log n). This lesson prepares you to implement faster solutions in coding interviews.

We'll cover the following...

Solution #1

Java
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 ...