Skip to content

1060. Missing Element in Sorted Array πŸ”’

Description

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.

 

Example 1:

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

Example 2:

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:

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 * 104
  • 1 <= nums[i] <= 107
  • nums is sorted in ascending order, and all the elements are unique.
  • 1 <= k <= 108

 

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

Solutions

Solution 1

Thinking

The array is sorted and distinct, so the number of missing values before index \(i\) is \(nums[i]-nums[0]-i\). A linear walk finds the \(k\)-th missing, but the follow-up asks for logarithmic time.

\(\textit{missing}(i)\) is increasing. If \(k\) exceeds the missing count at the end, the answer lies past the array; otherwise we bisect the least \(i\) with \(\textit{missing}(i)\ge k\) and add the leftover gap to \(nums[i-1]\).

The search range is \([0,n-1]\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
        def missing(i: int) -> int:
            return nums[i] - nums[0] - i

        n = len(nums)
        if k > missing(n - 1):
            return nums[n - 1] + k - missing(n - 1)
        l, r = 0, n - 1
        while l < r:
            mid = (l + r) >> 1
            if missing(mid) >= k:
                r = mid
            else:
                l = mid + 1
        return nums[l - 1] + k - missing(l - 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int missingElement(int[] nums, int k) {
        int n = nums.length;
        if (k > missing(nums, n - 1)) {
            return nums[n - 1] + k - missing(nums, n - 1);
        }
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (missing(nums, mid) >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l - 1] + k - missing(nums, l - 1);
    }

    private int missing(int[] nums, int i) {
        return nums[i] - nums[0] - i;
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func missingElement(nums []int, k int) int {
    missing := func(i int) int {
        return nums[i] - nums[0] - i
    }
    n := len(nums)
    if k > missing(n-1) {
        return nums[n-1] + k - missing(n-1)
    }
    l, r := 0, n-1
    for l < r {
        mid := (l + r) >> 1
        if missing(mid) >= k {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return nums[l-1] + k - missing(l-1)
}

Comments