LC: Missing Element in Sorted Array - spiralgo/algorithms GitHub Wiki

Missing Element in Sorted Array

The Essence:

How many elements are missing before some element in the array is related to the index of the element and the value of the element. It's basically the difference between the first element and the current element minus the number of previous, present elements (the index).

Because of this, the missing element count can only go up as the index increases.

Details:

Using this intuitions, once can binary search the array to find the smallest index where k values are missing and calculate the sought value.