Algorithms to Find the Missing Element in Sorted Array

Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.

Example 1:
Input: A = [4,7,9,10], K = 1
Output: 5
Explanation:
The first missing number is 5.

Example 2:
Input: A = [4,7,9,10], K = 3
Output: 8
Explanation:
The missing numbers are [5,6,8,…], hence the third missing number is 8.

Example 3:
Input: A = [1,2,4], K = 3
Output: 6
Explanation:
The missing numbers are [3,5,6,7,…], hence the third missing number is 6.

• 1 <= A.length <= 50000
• 1 <= A[i] <= 1e7
• 1 <= K <= 1e8

Brute Force O(N) Algorithm to Find the Missing Number in the Sorted Array

i.e. a at each iteration. If the current element does not match, we decrement K and to see if it becomes zero which we should know the current missing number a.

We move to the next element in the array only if it matches the current ‘desired’ number. Once the entire array is finished, that means the missing number is beyong the maximum number in the array – in this case, we simply return a + k – 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int a = nums[0];  
        int i = 0;
        while (i < nums.size()) {
            if (nums[i] != a) {
                if (--k == 0) return a;
            } else {
                i ++;
            }
            a ++;
        }
        return a + k - 1;
    }
};

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int a = nums[0];  
        int i = 0;
        while (i < nums.size()) {
            if (nums[i] != a) {
                if (--k == 0) return a;
            } else {
                i ++;
            }
            a ++;
        }
        return a + k - 1;
    }
};

Binary Search O(logN) Algorithm to Find the Missing Number in the Sorted Array

The numbers are already sorted, thus a hint to use the binary search algorithm which reduces the algorithm runtime complexity to O(logN).

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int n = nums.size();
        int i = 0, j = n;
        while (i < j) {
            int m = i + (j - i) / 2;
            nums[m] - m - k >= nums[0] ? j = m : i = m + 1;
        }
        return nums[0] + i + k - 1;
    }
};

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int n = nums.size();
        int i = 0, j = n;
        while (i < j) {
            int m = i + (j - i) / 2;
            nums[m] - m - k >= nums[0] ? j = m : i = m + 1;
        }
        return nums[0] + i + k - 1;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —