Problem

Given an integer array nums which is sorted in ascending order and all of its elements are unique and given also an integer k, return the kth missing number starting from the leftmost number of the array.

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

Input: nums = [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:

1
2
3

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

Constraints:

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 10^7
  • nums is sorted in ascending order, and all the elements are unique.
  • 1 <= k <= 10^8

Follow up: Can you find a logarithmic time complexity (i.e., O(log(n))) solution?

Solution

Method 1 – Binary Search for the kth Missing Number

Intuition

The missing numbers between elements can be counted by comparing the actual value and the expected value at each index. Binary search helps us quickly locate where the kth missing number falls, making the solution efficient for large arrays and large k.

Approach

  1. Define a helper to count missing numbers up to index i: nums[i] - nums[0] - i.
  2. If k is larger than all missing numbers in the array, return nums[n-1] + (k - missing(n-1)).
  3. Otherwise, use binary search to find the smallest index where missing(i) >= k.
  4. The answer is nums[left-1] + (k - missing(left-1)).

Code

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

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int n = nums.size();
        auto missing = [&](int i) { return nums[i] - nums[0] - i; };
        if (k > missing(n-1)) return nums[n-1] + k - missing(n-1);
        int left = 0, right = n-1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (missing(mid) < k) left = mid + 1;
            else right = mid;
        }
        return nums[left-1] + k - missing(left-1);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func MissingElement(nums []int, k int) int {
    n := len(nums)
    missing := func(i int) int { return nums[i] - nums[0] - i }
    if k > missing(n-1) {
        return nums[n-1] + k - missing(n-1)
    }
    left, right := 0, n-1
    for left < right {
        mid := left + (right-left)/2
        if missing(mid) < k {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return nums[left-1] + k - missing(left-1)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int missingElement(int[] nums, int k) {
        int n = nums.length;
        int missing = nums[n-1] - nums[0] - (n-1);
        if (k > missing) return nums[n-1] + k - missing;
        int left = 0, right = n-1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int miss = nums[mid] - nums[0] - mid;
            if (miss < k) left = mid + 1;
            else right = mid;
        }
        return nums[left-1] + k - (nums[left-1] - nums[0] - (left-1));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun missingElement(nums: IntArray, k: Int): Int {
        val n = nums.size
        fun missing(i: Int) = nums[i] - nums[0] - i
        if (k > missing(n-1)) return nums[n-1] + k - missing(n-1)
        var left = 0
        var right = n-1
        while (left < right) {
            val mid = left + (right - left) / 2
            if (missing(mid) < k) left = mid + 1 else right = mid
        }
        return nums[left-1] + k - missing(left-1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from typing import List
class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
        n = len(nums)
        def missing(i: int) -> int:
            return nums[i] - nums[0] - i
        if k > missing(n-1):
            return nums[-1] + k - missing(n-1)
        left, right = 0, n-1
        while left < right:
            mid = left + (right - left) // 2
            if missing(mid) < k:
                left = mid + 1
            else:
                right = mid
        return nums[left-1] + k - missing(left-1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn missing_element(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let missing = |i: usize| nums[i] - nums[0] - i as i32;
        if k > missing(n-1) {
            return nums[n-1] + k - missing(n-1);
        }
        let (mut left, mut right) = (0, n-1);
        while left < right {
            let mid = left + (right - left) / 2;
            if missing(mid) < k {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        nums[left-1] + k - missing(left-1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    missingElement(nums: number[], k: number): number {
        const n = nums.length;
        const missing = (i: number) => nums[i] - nums[0] - i;
        if (k > missing(n-1)) return nums[n-1] + k - missing(n-1);
        let left = 0, right = n-1;
        while (left < right) {
            const mid = left + Math.floor((right - left) / 2);
            if (missing(mid) < k) left = mid + 1;
            else right = mid;
        }
        return nums[left-1] + k - missing(left-1);
    }
}

Complexity

  • ⏰ Time complexity: O(log n) — Binary search is used to find the position efficiently.
  • 🧺 Space complexity: O(1) — Only a few variables are used for computation.