How to Find Missing Number in a Sorted Array in Java [Solved] (original) (raw)

Today's coding problem is not very new, it's an age-old classic Programming interview Question. You have a sorted array containing n - 1 unique number starting from 0 to n - 1. There is only one number missing in this range and you need to find that out. I mean you need to write a Java method to find the missing number and print its value in the console. Some of you might have seen this question before, but if you have not been asked this question before, what is the first approach comes into your mind to solve this question? Since only one number is missing, many programmers come up with the approach of iterating over the array, and comparing each element with the expected one like the first element should be 0, the second element should be 1, and so on.

Though this will solve the problem, it will cost you O(n) time. I mean time complexity of your solution would be O(n) which is not good for a big array, like with 100 million entries. What can you do to improve performance?

The key here is that you already have a sorted array, do you think our earlier solution is taking full advantage of this knowledge, well it is but not fully.

What it is doing is performing a linear search which is costing O(n), but if you do a binary search, which of course needs a sorted array, we can reduce the time taken in the range of O(logN).

Since numbers are in the range from 0 to n - 1 and are sorted, the first number till the missing one should be the same as their indexes. I mean if 0 is not missing, then it must be in the first index, I mean at 0.

If you generalize this, you will find out that if the missing number is k then all numbers less than k are located in an array with indexes the same as their value.

Also, number k + 1 will be located at index k, and number k + 2 will be located at index k + 1. What does this mean? Well, it means that the missing number is the first cell whose value is not the same as its index. So our problem reduces to search in an array to find the first cell, whose value is not the same as its index.

You can easily find out this by using the binary search algorithm in O(logN) time. Our solution implements this logic to find the missing integer in a sorted array in Java. You can use this solution to find the missing number in an array of numbers 1-1000 or 1 -100.

This problem also shows that having a good knowledge of fundamental data structure is essential to solve any coding problems. Therefore, you must spend some time brushing up your Data Structure skills before you go for an interview.

If you need a course, I highly recommend Data Structure and Algorithms in Java: Deep Dive on Udemy. It's both comprehensive and enjoyable and also very affordable. You can buy it for just $10 on Udemy sale.

How to Find Missing Number in Sorted Array- Solution

Here is our complete solution to this problem. As discussed in the first paragraph, the solution is based upon a binary search algorithm and that's why its complexity is in logarithmic order.

If you asked this question in the interview, you must write production-quality code, which means is handling invalid input and boundary conditions.

In our method, we are checking whether the array is not null and empty before proceeding further. If you are not familiar with the binary search algorithm then this diagram will help you with how does it work. In binary search, instead of starting from the front, we start from the middle element.

If the middle element is greater than the expected number is on the left-hand side of a middle element (lower array), otherwise, it is on the right-hand side (higher array). So in each iteration, we end up reducing our problem set by half.

So in the start, if you have 16 elements in the array, next iteration you only need to search in 8 elements and subsequently 4 and 2, this is how we get O(logN) complexity.

This problem also shows that knowledge of coding patterns is very important for coding interviews.

If you know the pattern you can solve many unseen problems and that's why you should spend some time solving coding problems to build that pattern recognition logic in your mind. A course like Grokking the Coding Interview: Patterns for Coding Questions is really a godsend course for someone who wants to master these patterns. It will teach you 15 popular coding patterns to interview questions which means you can tackle most of the unseen problems during interviews.

Java Program to find the missing number in a sorted Integer array

And, here is our code example to find the missing integer in a sorted array or series.

import java.util.Arrays; /**

Java Program to find the missing number in a sorted array
with integers in range 0 to n -1
@author Javin Paul */ public class MissingNumberFinder {

public static void main(String args[]) {
```
 System.out.println("Test #1 : Missing number in sorted array ");
 int[] input = new int[]{1, 2, 3, 4, 6};
 int missing = missingNumberFromSortedArray(input);
 System.out.println("Missing number from array : " 
           + Arrays.toString(input) + " is : " + missing);
```
}

public static int missingNumberFromSortedArray(int[] numbers) { if (numbers == null || numbers.length <= 0) { throw new IllegalArgumentException("Null or Empty array not permitted"); } int left = 0; int right = numbers.length - 1; while (left <= right) { int middle = (right + left) >> 1; if (numbers[middle] != middle) { if (middle == 0 || numbers[middle - 1] == middle - 1) { return middle; } right = middle - 1; } else { left = middle + 1; } } throw new RuntimeException("No missing number"); }

}

Output: Test #1 : Missing number in sorted array Missing number from array : [1, 2, 3, 4, 6] is : 0

That's all about how do you find the missing integer in an array of 0 to n - 1. Remember you can also solve this problem with linear search and there is nothing wrong if you first come up with that solution, in fact, it's very natural, but you must pay attention to the sorted word.

Binary search and sorted array go hand in hand. When it comes to improving the search algorithms, binary search always better than linear search.

Always remember to discuss your solution with interviewer, discussion is more important than just solving the problem as it give you a chance to showcase your talent, skill, thought process, and attention to detail to interviewer and impress them.

Also don't settle for N^2 complexity, a great developer never settle for that unless you have real concern like memory, always try to find a better solution using memory and CPU trade off.

Other Programming Interview Questions and Articles for Java developers

How to reverse an array in place in Java? (solution)
Top 5 Courses to learn Data Structure and Algorithms (courses)
Top 50 Data Structure and Algorithms Interview Questions (list)
How to check if an array contains a particular value? (solution)
Top 5 Books to learn Data Structure and Algorithms (Books)
How to find all pairs in an array whose sum is equal to k (solution)
Top 5 Courses to learn Dynamic Programming for Interviews (courses)
How to find the largest and smallest number in an array without sorting? (solution)
How to find one missing number in a sorted array? (solution)
Top 30 linked list coding interview questions (see here)
Top 50 Java Programs from Coding Interviews (see here)
5 Free Data Structure and Algorithms Courses for Programmers (courses)
10 Algorithms Books Every Programmer Should Read (books)
How to remove an element from an array in Java? (solution)
How do find the top 2 numbers from a given array? (solution)
10 Free Data Structure and Algorithm Courses for Programmers (courses)
100+ Data Structure Coding Problems from Interviews (questions)
How to sort an array using bubble sort in Java? (solution)
How to find duplicates from an unsorted array in Java? (solution)
How to remove duplicates from an array in Java? (solution)

Thanks for reading this article so far. If you like this array-based coding problem then please share it with your friends and colleagues. If you have any questions or doubt then please let us know and I'll try to find an answer for you. As always suggestions, comments, innovative and better answers are most welcome.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Data Structure in Java free course on Udemy. It's completely free and all you need to do is create a free Udemy account to enroll in this course.

P. P. S. - If you want more of such questions from tech interviews, please see Cracking the Coding Interview 6th Edition, it contains over 190 coding questions from different software companies, startups, investment banks, and service-based companies.