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

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

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int missingElement(vector<int>& nums, int k) {\n        int n = nums.size();\n        auto missing = [&](int i) { return nums[i] - nums[0] - i; };\n        if (k > missing(n-1)) return nums[n-1] + k - missing(n-1);\n        int left = 0, right = n-1;\n        while (left < right) {\n            int mid = left + (right - left) / 2;\n            if (missing(mid) < k) left = mid + 1;\n            else right = mid;\n        }\n        return nums[left-1] + k - missing(left-1);\n    }\n};","lang":"cpp"},{"language":"Go","code":"func MissingElement(nums []int, k int) int {\n    n := len(nums)\n    missing := func(i int) int { return nums[i] - nums[0] - i }\n    if k > missing(n-1) {\n        return nums[n-1] + k - missing(n-1)\n    }\n    left, right := 0, n-1\n    for left < right {\n        mid := left + (right-left)/2\n        if missing(mid) < k {\n            left = mid + 1\n        } else {\n            right = mid\n        }\n    }\n    return nums[left-1] + k - missing(left-1)\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int missingElement(int[] nums, int k) {\n        int n = nums.length;\n        int missing = nums[n-1] - nums[0] - (n-1);\n        if (k > missing) return nums[n-1] + k - missing;\n        int left = 0, right = n-1;\n        while (left < right) {\n            int mid = left + (right - left) / 2;\n            int miss = nums[mid] - nums[0] - mid;\n            if (miss < k) left = mid + 1;\n            else right = mid;\n        }\n        return nums[left-1] + k - (nums[left-1] - nums[0] - (left-1));\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun missingElement(nums: IntArray, k: Int): Int {\n        val n = nums.size\n        fun missing(i: Int) = nums[i] - nums[0] - i\n        if (k > missing(n-1)) return nums[n-1] + k - missing(n-1)\n        var left = 0\n        var right = n-1\n        while (left < right) {\n            val mid = left + (right - left) / 2\n            if (missing(mid) < k) left = mid + 1 else right = mid\n        }\n        return nums[left-1] + k - missing(left-1)\n    }\n}","lang":"kotlin"},{"language":"Python","code":"from typing import List\nclass Solution:\n    def missingElement(self, nums: List[int], k: int) -> int:\n        n = len(nums)\n        def missing(i: int) -> int:\n            return nums[i] - nums[0] - i\n        if k > missing(n-1):\n            return nums[-1] + k - missing(n-1)\n        left, right = 0, n-1\n        while left < right:\n            mid = left + (right - left) // 2\n            if missing(mid) < k:\n                left = mid + 1\n            else:\n                right = mid\n        return nums[left-1] + k - missing(left-1)","lang":"python"},{"language":"Rust","code":"impl Solution {\n    pub fn missing_element(nums: Vec<i32>, k: i32) -> i32 {\n        let n = nums.len();\n        let missing = |i: usize| nums[i] - n

Related Tags