Practice/Meta/Leetcode 1060. Missing Element in Sorted Array

Leetcode 1060. Missing Element in Sorted Array

CodingMust

Problem

You are given a strictly increasing integer array nums and a positive integer k. The array contains gaps - there are integers missing between consecutive elements and potentially before the first element.

Your task is to find the k-th positive integer that is missing from the array. The missing numbers start counting from 1 and include all positive integers not present in nums.

Requirements

1. Return the k-th positive integer that does not appear in nums
2. The array nums is guaranteed to be sorted in strictly increasing order
3. All elements in nums are positive integers
4. You should aim for better than O(n) time complexity where possible

Constraints

• 1 ≤ nums.length ≤ 5000
• 1 ≤ nums[i] ≤ 10^9
• nums is sorted in strictly increasing order
• 1 ≤ k ≤ 10^8

Examples

Example 1:

Input: nums = [2, 4, 6, 8], k = 3 Output: 5 Explanation: The missing positive integers are [1, 3, 5, 7, 9, 10, 11, ...]. The 3rd missing number is 5.

Example 2:

Input: nums = [5], k = 2 Output: 2 Explanation: Missing numbers before 5 are [1, 2, 3, 4]. The 2nd one is 2.

Example 3:

Input: nums = [1, 2, 3, 4], k = 2 Output: 6 Explanation: The array is consecutive from 1 to 4, so the first missing number is 5 and the second is 6.