[LeetCode] Missing Element in Sorted Array

1060. Missing Element in Sorted Array

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int missingElement(vector<int>& nums, int k) {
int l = 0, r = nums.size() - 1;
while(l < r) {
int m = l + (r - l) / 2;
int alpha = nums[m] - (m + nums[0]); //how many skips
if(alpha < k) {
l = m + 1;
} else {
r = m - 1;
}
}
int diff = nums[l] - (l + nums[0]) - k;
if(diff >= 0) return nums[l] - diff - 1;
return nums[l] - diff;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/23/PS/LeetCode/missing-element-in-sorted-array/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.